[Baekjoon] 18352_특정 거리의 도시 찾기

Silver II

문제(출처: https://www.acmicpc.net/problem/18352)

---

<특정 거리의 도시 찾기>

문제 

 

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.
이때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.
예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

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

 

 

입력

 

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

 

출력 

 

X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다. 이때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

 

 

문제 풀이

- 초기 코드: 시간 초과

import sys

def bfs(graph, start, depth):
    visited=[start]
    queue=[start]
    while queue:
        temp=queue.pop(0)
        for i in graph[temp]:
            if i not in visited:
                visited.append(i)
                depth[i]=depth[temp]+1
                queue.append(i)

if __name__=='__main__':
    #도시의 개수, 도로의 개수, 거리 정보, 출발 도시의 번호
    N,M,K,X=map(int,sys.stdin.readline().split())

    graph={}
    depth={}
    for i in range(N):
        graph[i+1]=[]
        depth[i+1]=0

    for i in range(M):
        A,B=map(int,sys.stdin.readline().split())
        graph[A].append(B)

    bfs(graph,X,depth)

    result=[]
    for key,value in depth.items():
        if value==K:
            result.append(key)

    if len(result)==0:
        print(-1)
    else:
        result.sort()
        for i in result:
            print(i)

 

첫 도전... 또 시간 초과가 발생했다. 더는 생각나지 않아 잠시 내버려 두고 다른 문제를 풀었었다. 그 문제를 통해 해결 방법이 떠올라 다시 도전 -!

 

❓ 왜 시간 초과가 발생했는가?

depth로 충분히 방문 여부를 확인할 수 있음에도 visited 리스트를 만들어 방문 여부를 확인하였다. 여기서 시간 초과가 발생했다고 생각했다.

 

위의 문제점을 코친 코드이다.

 

- 두 번째 코드: 시간 초과

import sys

def bfs(graph, start, depth):
    queue=[start]
    while queue:
        temp=queue.pop(0)
        for i in graph[temp]:
            if depth[i]==0 and i!=start:
                depth[i]=depth[temp]+1
                queue.append(i)

if __name__=='__main__':
    #도시의 개수, 도로의 개수, 거리 정보, 출발 도시의 번호
    N,M,K,X=map(int,sys.stdin.readline().split())

    graph={}
    depth={}
    for i in range(N):
        graph[i+1]=[]
        depth[i+1]=0

    for i in range(M):
        A,B=map(int,sys.stdin.readline().split())
        graph[A].append(B)

    bfs(graph,X,depth)

    result=[]
    for key,value in depth.items():
        if value==K:
            result.append(key)

    if len(result)==0:
        print(-1)
    else:
        result.sort()
        for i in result:
            print(i)

 

내가 생각한 문제점을 고쳤음에도 시간 초과가 발생했다.

 

❓ 왜 시간 초과가 발생했는가?

이번에는 이유를 찾지 못해 검색의 힘을 빌렸다. 찾아본 결과 list를 deque로 사용하면 해결할 수 있을 것 같았다.

 

 

- my solution

import sys
from collections import deque

def bfs(graph, start, depth):
    queue=deque([start])
    while queue:
        temp=queue.popleft()
        for i in graph[temp]:
            if depth[i]==0 and i!=start: #아직 방문하지 않았으면
                depth[i]=depth[temp]+1
                queue.append(i)

if __name__=='__main__':
    #도시의 개수, 도로의 개수, 거리 정보, 출발 도시의 번호
    N,M,K,X=map(int,sys.stdin.readline().split())

    graph={}
    depth={}
    for i in range(N):
        graph[i+1]=[]
        depth[i+1]=0

    for i in range(M):
        A,B=map(int,sys.stdin.readline().split())
        graph[A].append(B)

    bfs(graph,X,depth)

    result=[]
    for i in range(N):
        if depth[i+1]==K: # 최단 거리가 K
            result.append(i+1)

    if len(result)==0: # 하나도 존재하지 않으면
        print(-1)
    else: # 도시의 번호를 오름차순으로 출력
        result.sort()
        for i in result:
            print(i)

 

• bfs
  - queue: deque로 선언
  - queue가 빌 때까지 반복: 젤 처음 값 pop 해서 그와 연결된 이웃 도시에 방문하지 않았다면 거리(현재 도시 depth의 +1) 저장 및 queue에 추가
• main
  - 입력
  - graph: dict, 도시 연결 그래프
  - depth: dict, 거리 정보 저장
  - 방향 있는 그래프
  - bfs 호출
  - depth 순회를 통해 최단 거리 K와 같은 도시가 있다면 result에 추가 -> 하나도 존재하지 않으면 -1 출력/ 존재하면 도시의 번호를 오름차순으로 출력

---

생각🤔

 

시간 초과에서 벗어나지 못할 줄 알았지만... deque를 통해 탈출 완료 -!

기억하자 deque -!

 

---