15_특정 거리의 도시 찾기

18352번: 특정 거리의 도시 찾기

 

BFS 문제다.

문제에서 모든 도로의 거리는 1이라고 했으니, 모든 간선의 비용이 1인 것이다.

이럴 때는 BFS를 활용해서 최단 거리를 구할 수 있다.(간선의 비용이 다른 경우에는 다익스트라)

 

노드의 개수 N은 300,000 이하이고, 간선의 개수 M은 1,000,000 이하이므로,

시간 복잡도는 O(N+M)에 의해 완전완전 가능하다.

기초적인 BFS 구현을 통해 풀 수 있는 문제다.

 

---

풀이 코드

# 18352번: 특정 거리의 도시 찾기
from collections import deque
import sys

input = sys.stdin.readline

n, m, k, x = map(int ,input().split())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1) # 방문 여부를 저장하는 리스트(0이면 방문x, 나머지는 방문까지의 거리)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

def bfs():
    queue = deque([x]) # 시작점을 큐에 넣고 시작
    visited[x] = 1 # 시작 점을 방문 처리
    while queue:
        now = queue.popleft()
        for i in graph[now]:
            if visited[i] == 0:
                queue.append(i)
                visited[i] = visited[now] + 1

    # visited 배열에 저장된 수들은 시작점에서의 최단거리 + 1인 값임
    # 그러므로 k+1을 확인해야 함
    answer = []
    for i in range(1, n+1):
        if visited[i] == k+1:
            answer.append(i)

    return answer


result = bfs()

if len(result) == 0:
    print(-1)
else:
    for num in result:
        print(num)

 

정답 로직 출력부분을 약간 수정해 이런식으로 하면 더 깔끔하게 답을 구할 수 있다.

...

def bfs():
    queue = deque([x]) # 시작점을 큐에 넣고 시작
    visited[x] = 1 # 시작 점을 방문 처리
    while queue:
        now = queue.popleft()
        for i in graph[now]:
            if visited[i] == 0:
                queue.append(i)
                visited[i] = visited[now] + 1


bfs()

check = False
for i in range(1, n+1):
    # visited 배열에 저장된 수들은 시작점에서의 최단거리 + 1인 값임
    # 그러므로 k+1을 확인해야 함
    if visited[i] == k+1:
        print(i)
        check = True

if not check:
    print(-1)