[Python] 백준 24479번: - 알고리즘 수업 - 깊이 우선 탐색 1

🔗 문제 링크

백준 24479번: 알고리즘 수업 - 깊이 우선 탐색 1

⏰ 소요된 시간

20분

🛡️ 난이도

실버 2

✨ 수도 코드

전체 코드

import sys
sys.setrecursionlimit(10**6)
input = open(0).readline

num = 1

def dfs(node, nodes, visited, num):
    visited[node-1] = num
    num += 1
    for i in sorted(nodes[node-1]):
        if not visited[i-1]:  # 방문한 적이 없다면
            num = dfs(i, nodes, visited, num)

    return num

node_cnt, edge_cnt, start_node = map(int, input().split())
nodes = [[] for _ in range(node_cnt)]
visited = [0 for _ in range(node_cnt)]

for i in range(edge_cnt):
    a, b = map(int, input().split())
    nodes[a-1].append(b)
    nodes[b-1].append(a)

dfs(start_node, nodes, visited, num)

for n in visited:
    print(n)

주어진 테스트케이스는 잘 통과하는데 틀렸습니다가 떴다. 그래서 질문 게시판에서 찾은 반례로 해결하였다. 틀렸던 이유는 재귀적으로 dfs 함수를 호출하면서 num 변수가 올바른 순서로 갱신되지 않아서였다.

반례

# 입력
5 6 1
1 4
1 2
2 3
2 4
3 4
5 1

# 정답
1
2
3
4
5

# 나의 출력
1
2
3
4
3

참고) 처음 작성했던 dfs 함수 코드

def dfs(node, nodes, visited, num):
    visited[node-1] = num
    for i in sorted(nodes[node-1]):
        if not visited[i-1]:  # 방문한 적이 없다면
            visited[i-1] = num
            num += 1
            dfs(i, nodes, visited, num)

    return visited