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

오랜만에 백준을 풀었다.

스트릭이 끊긴 이후로 안 풀다가 코테 준비도 해야하고 PS는 꾸준히 하는 게 좋을 것 같아서 다시 시작하였다.

파이팅 ^ㅁ^

---

https://www.acmicpc.net/problem/24479

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

허나 웬 걸.. Recursion Error가 떴고 코드 위에 아래의 코드를 추가하여 재귀의 깊이를 더 깊게 만들어주었다. 그러니 Recursion Error가 발생하지는 않았다.

sys.setrecursionlimit(10 ** 6)

하지만 그 후에는 3%에 '틀렸습니다'라고 뜨는게 아닌가... 

https://www.acmicpc.net/board/view/97648

글 읽기 - 3% 오류 반례 공유합니다.

# 알고리즘 수업 - 깊이 우선 탐색 1
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
def dfs(visited, maps, R, ans):
    visited[R] = ans
    ans += 1
    for i in maps[R]:
        if visited[i] == 0:
            dfs(visited, maps, i, ans)

def main():
    N, M, R = map(int, input().split())
    maps = [[] for _ in range(N+1)]
    visited = [0 for _ in range(N+1)]
    ans = 1
    for _ in range(M):
        a, b = map(int, input().split())
        maps[a].append(b)
        maps[b].append(a)
    for i in range(1, N+1):
        maps[i].sort()
    dfs(visited, maps, R, ans)
    
    for a in visited[1:]:
        print(a)
if __name__ == "__main__":
    main()

위의 글의 반례를 넣어봤더니 정답과 다른 .. 값이 출력됐다

1
0
0
2
4
3

이 정답인데

1

0

0

2

2

3

이라니~? 그래도 반례를 찾았으니 열심히 어디가 틀렸는지 코드를 뜯어보았다.

6번째 행부터 11번째 행까지 dfs 함수 내에서 디버깅을 위해 출력해본 결과이다.

print(R, "      ", maps[R], "      ", i, "       ", visited)

1번째 노드에서 4번째 노드로 이동한 후, 연결된 경로를 다 지난 뒤 다시 1번째 노드에서 5번째 노드로 이동할 때 ans값이 갱신되지 않아 기존 2값이 그대로 출력된 것이다.

이는 dfs 함수 인자로 ans를 가져와 출력하는 코드이기 때문에 발생했다.

따라서 ans를 전역변수로 선언한 뒤 값을 증가시켜줬더니 반례를 통과하였다.

성공!

제출한 코드는 다음과 같다.

# 알고리즘 수업 - 깊이 우선 탐색 1
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def dfs(visited, maps, R):
    global ans
    visited[R] = ans
    ans += 1
    for i in maps[R]:
        if visited[i] == 0:
            dfs(visited, maps, i)

N, M, R = map(int, input().split())
maps = [[] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
ans = 1

for _ in range(M):
    a, b = map(int, input().split())
    maps[a].append(b)
    maps[b].append(a)
for i in range(1, N+1):
    maps[i].sort()
dfs(visited, maps, R)

for a in visited[1:]:
    print(a)