[DFS] BOJ_13023 ABCDE

DFS 연습1 - BOJ_13023 ABCDE

# BOJ_13023 ABCDE

def dfs(v, depth):
    print("{}번째 노드 호출됨".format(v))
    global done
    if depth == 4 or done:
        done = True
        return True

    visited[v] = True
    # v에 연결된 자식노드들 u
    for u in graph[v]:
        # 자식노드 이미 발견했으면 다른자식 찾으러가셈
        if visited[u]: continue
        dfs(u, depth+1)

    # 자식노드의 끝까지 판 다음에 다시 올라가게 하기위해서
    visited[v] = False


N, M = map(int, input().split())
graph = [[] for _ in range(N)]
done = False

# 그래프 생성
for _ in range(M):
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)

visited = [False] * N

print(graph)


for v in range(N):
    if not visited[v]:
        dfs(v, 0)
    if done: break


print("1") if done else print("0")

print(visited)




'''
6 6
0 1
1 2
2 0
3 4
4 5
5 3

정답: 0
'''

'''
7 5
0 1
2 3
3 4
4 5
5 6

정답: 1
'''

'''
6 5
1 2
2 4
2 3
3 4
4 5

정답: 1
'''

def(v, depth )에서 마지막에 visited[v] = false 하는 이유

사이클이 있는 그래프이기 때문이다.

1) 1-2-4-5

2) 1-2-3-4-5

이런 경로로 갈 수 있는데 1) 탐색에서 5를 visited 처리해버리면

2) 탐색에서 5를 갈 수 없다. 그래서 탐색 이후에는 visited[현재 노드] = false 처리한다.