[백준] 18352번 특정 거리의 도시 찾기 - BFS(Python3)

문제

 

입력과 출력

제한 조건과 설계

제한 조건

1. 시간 제한이 2초지만 노드가 30만개라서 좀 불안하다.
2. 방향 그래프다.
3. 시작 노드로부터 모든 각 노드의 거리를 구하는 것이므로 BFS가 좋아보인다.

---

자연어 알고리즘

1. 정보를 입력 받아 그래프를 생성한다.
2. 시작 정점으로 BFS 탐색을 시도한다.
   • queue에서 front 노드를 dequeue한다.
   • dequeue된 노드의 인접한 노드 중에서 아직 방문하지 않은 노드가 있다면
     • queue에 인접 노드를 enqueue 한다.
     • 시작 노드로부터 인접 노드의 거리 = 시작 노드로부터 이전 노드(dequeue된 노드)의 거리 + 1
   • queue가 빌 때까지 위의 과정을 반복한다.
3. 선형 탐색으로 nodes_dist에서 요소 값이 k(거리)인 index를 ans리스트에 append 한다.
4. 답에 해당하는 노드들을 출력한다. 답에 해당하는 노드가 없다면 -1을 출력한다.
5. 종료

---

파이썬 코드

import sys
from collections import deque

input = sys.stdin.readlineㅅd 

# 도시의 개수, 도로의 개수, 거리, 시작 정점
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
nodes_dist = [0] * (n+1)

for i in range(m):
    u,v= map(int, input().split())
    graph[u].append(v)
    graph[u].sort()

def bfs(graph, s, visited):
    queue = deque([s])
    visited[s] = True

    while queue:
        previous_node = queue.popleft()
        for node in graph[previous_node]:
            if not visited[node]:
                queue.append(node)
                nodes_dist[node] = nodes_dist[previous_node] + 1
                visited[node] = True
        
        
bfs(graph,x,visited)

ans = [idx for idx in range(1, n+1) if nodes_dist[idx] == k]

if ans:
    print(*ans, sep='\n')
else:
    print(-1)

---

세 줄 요약

1. 어떤 한 노드로부터 다른 모든 노드의 거리를 구할 때는 BFS를 선택하자. (어떤 노드와 어떤 노드의 거리면 DFS가 더 좋다.)
2. 언패킹 연산자(*)는 iterable 객체의 개별 항목을 추출하여 개별 인자로 전달한다. 여기서 sep은 개별 항목의 구분자이다.
3. queue에 들어가는 순간 방문될 예정이므로 방문 처리를 해야 한다.