[백준] 18352번: 특정 거리의 도시 찾기(Python) | LIM

1. 문제
2. 첫 번째 시도( 메모리 초과 발생 )
3. 두 번째 시도( 시간 초과 발생 )
3. 세 번째 시도( 틀린 원인과 정답 )

📚 문제

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

 

👩‍💻 첫 번째 시도 -> 메모리 초과 발생

이렇게 하니 자꾸 메모리 초과가 떴다. 문제는 굳이 해당 노드에 연결된 노드번호만 넣어주면 되는 걸 굳이 배열의 길이를 늘려서 모든 노드를 다 넣어주었기 떄문이다. 이런 부분을 주의해야하는 것 같다.

 

roads = [[0] * (N+1) for _ in range(N+1)]

 

이 부분이 자꾸 메모리 초과를 일으켰던 것이다. 

 

👩‍💻 두 번째 시도 -> 시간 초과 발생

이 때 시간 초과가 발생한 이유는 단순히 입력을 받을 때 input() 으로 받기 때문이었다. 

문제를 보면 최대 1,000,000개 입력받을 수 있어야 하는데 시간제한이 2초이므로 input() 을 사용하면 시간초과로 인하여 통과하지 못한다.
따라서 일정량 이상의 입력은 sys.stdin.readline().split() 을 사용하면 좋다. 이것 때문에 또 20분 가까이 날린 것 같다..흑흑

 

👩‍💻 세 번째 시도 -> 그냥 틀림

슬슬 화가 났다. 뒤에 정답 풀이를 봤을때 나의 풀이와 전혀 다른 점이 없어보였다. 코드 구성이 거의 똑같았다.

혹시 하는 마음에 정답과 유일하게 다른 visited 배열에 방문하지 않은 노드들을 0에서 -1 로 바꾸어보았다.

드디어 맞을 수 있었다..

아무래도 처음에 방문하지 않은 모든 도시들을 0으로 설정했고 처음 시작하는 도시도 0부터 시작하다 보니 특정 예제에서 예외가 생긴게 아닌건가 싶다..

 

혹시 모르니 늘 방문처리를 해야 하는 문제가 생기면 방문하지 않은 도시들, 방문한 도시들을 정확히 구분하도록 하자