DFS
깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
Last updated
깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
Last updated
#DFS 메소드 정의
def dfs(graph, v, visited):
#현재 노드를 방문처리
visited[v] = True
print(v, end=' ')
#현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
#각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
[1, 2], #0번 노드에서 1, 2로 이동 가능하다.
[3, 4, 5], #1번 노드에서 3, 4, 5로 이동 가능하다.
[6, 7], #2번 노드에서 6, 7로 이동 가능하다.
[8],
[3],
[],
[],
[],
[]
]
#각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
dfs(graph, 0, visited) #출력 : 0 1 3 8 4 5 2 6 7
N,M=map(int,input().split())
arr=[[] for _ in range(N)]
for _ in range(M):
a,b=map(int,input().split())
arr[a].append(b)
arr[b].append(a)
def dfs(index,depth):
if depth==4: #한 번이라도 depth가 4인 노드가 있다면 1을 출력하고 끝낸다.
print(1);
exit();
for i in arr[index]:
if not visited[i]:
visited[i]=1
dfs(i,depth+1)
visited[i]=0
visited=[0]*N
for i in range(N):
#방문표시
visited[i]=1
dfs(i,0)
#방문표시 해제
visited[i]=0
print(0)