99클럽 코테 스터디 37일차 TIL : DFS 문제 풀이

 

• 문제

 

• 연습코드

n,m= map(int,input().split())
g=[[0]*(n+1) for _ in range(n+1)]
#1번부터 n번까지 있어야하므로 n+1개를 만들어야지 0번부터 .n번까지 인덱스 번호가 생긴다 .
#(n+1)(n+1) 2차원 리스트를 만들어야지 n번 인덱스까지 생긴다

for i in range(m):
  a,b=map(int,input().split())
  g[a][b]=1
  g[b][a]=1


for i in range(1,n+1):
  for j in range(1,n+1):
    print(g[i][j], end=' ')
  print()

##포문을 1부터 n+1까지만 돌려서 1행부터 n행까지 출력한다

 

 

 

• 설명 및 개념

 

💡 그래프 = 노드와 간선의 집합 

💡 가중치 방향그래프 = 간선에 값이 있고 방향이 있다

💡 2차원리스트를 사용하여 그래프를 코드로 나타낸다

💡 행과열을 노드의 번호라고 생각한다

(1,2)를 1로 체크하면 1번 노드에서 2번노드로 갈 수 있다라는 뜻이다 . 1 --> 2

행번호에서 열번호로 이동한다고 생각한다

 

• 코드

n,m= map(int,input().split())
g=[[0]*(n+1) for _ in range(n+1)]

for i in range(m):
  a,b,c=map(int,input().split())
  g[a][b]=c
  

for i in range(1,n+1):
  for j in range(1,n+1):
    print(g[i][j], end=' ')
  print()

 

 

 

---

---

 

 

• 문제

 

 

 

 

 

 

•  코드 

def DFS(v):
  global cnt
  if v==n:
    cnt+=1
  else:
    for i in range(1,n+1):
      if ch[i]==0 and g[v][i]==1:
        ch[i]=1
        DFS(i)
        ch[i]=0



n,m=map(int,input().split())
g=[[0]*(n+1) for _ in range(n+1)]
cnt=0
ch=[0]*(n+1)
for i in range(m):
  a,b=map(int,input().split())
  g[a][b]=1
DFS(1)