[백준 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을 출력한다.

 

입력 예시

4 4 2 1 
1 2 
1 3 
2 3 
2 4

 

출력 예시

4

 

---

내 풀이 - test case 통과 but 시간 초과

from collections import deque

n, m, k, x = map(int, input().split())

graph = [[] for _ in range(n + 1)]

# 모든 도로 정보 입력 받기
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

# 방문 처리를 기록할 리스트를 생성
visited = [False] * (n + 1)


# BFS 메서드를 정의
def bfs(k):
    # 출발 도시를 queue에 삽입하고 방문 처리
    queue = deque([x])
    visited[x] = True
    v_list = []
    # k번 만큼 탐색
    for _ in range(k):
        # queue가 빌 때까지 queue에 있는 노드를 꺼내서 v_list에 담음
        while queue:
            v = queue.popleft()
            v_list.append(v)
        # v_list의 노드들에서 갈 수 있는 인접 노드 탐색
        for i in v_list:
            for j in graph[i]:
                # 인접노드가 방문하지 않은 노드라면 queue 삽입하고 방문 처리
                if not visited[j]:
                    queue.append(j)
                    visited[j] = True
        # v_list 리스트를 비움
        v_list.clear()

    # 만일 queue에 최단 거리가 K인 도시가 담겨 있지 않다면 queue에 -1을 삽입함
    if not queue:
        queue.append(-1)

    # 최단 거리가 K인 도시들이 담긴 queue를 리스트화하고 오름차순으로 정리
    result = sorted(list(queue))

    return result


result = bfs(k)

for i in result:
    print(i)
 

 

지향할 답안

from collections import deque

n, m, k, x = map(int, input().split())

graph = [[] for _ in range(n + 1)]

# 모든 도로 정보 입력 받기
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

# 모든 도시에 대한 최단 거리 초기화
distance = [-1] * (n + 1)
distance[x] = 0  # 출발 도시의 최단 거리는 0으로 설정

# BFS 수행
q = deque([x])
while q:
    now = q.popleft()
    # 현재 도시에서 이동 가능한 도시 확인
    for next_node in graph[now]:
        # 아직 방문하지 않은 도시라면
        if distance[next_node] == -1:
            # 최단 거리 갱신
            distance[next_node] = distance[now] + 1
            q.append(next_node)

# 최단 거리가 K인 모든 도시를 오름차순으로 출력
check = False
for i in range(1, n + 1):
    if distance[i] == k:
        print(i)
        check = True

# 최단 거리가 K인 도시가 없다면, -1을 출력
if not check:
    print(-1)

 

문제점

구현은 했어도 3중 for문을 사용해 시간이 초과됐다. 코드 논리도 명확하게 눈에 들어오진 않는다.

 

고려해 볼 점

완전 탐색 문제가 아니라면 최대한 3중 for문을 피하자.