[BOJ/Python] 특정 거리의 도시 찾기 || DFS, BFS
백준 18352 특정 거리의 도시 찾기 파이썬
18352번: 특정 거리의 도시 찾기
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개
www.acmicpc.net
❍ 문제
어떤 나라에는 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을 출력한다.
❏ 문제 풀이
모든 도로의 거리는 1이다.
모든 간선의 비용이 동일할 때, BFS를 이용하면 최단 거리를 구할 수 있다.
따라서, BFS를 통해 모든 도시와의 최단 거리를 구하고, 그 중에서 K와 일치하는 도시만을 출력하면 된다.
❍ 변수 설명
import sys
from collections import deque
input = sys.stdin.readline
# 도시의 개수, 도로의 개수, 거리 정보, 출발 도시의 번호
n, m, k, x = map(int, input().split())
# 도로
road = [[] for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, input().split())
road[a].append(b)
visited = [False] * (n + 1)
visited[x] = True
# bfs로 최단 거리 찾기
# result = [-1] * (n + 1)
# result[x] = 0
result = [0] * (n + 1)
단방향으로 도로를 알려주므로 road[a].append(b)로 a → b 방향으로 연결을 해준다.
visited는 방문이 된 도시인지를 확인하는 리스트로, 시작 도시인 x는 방문 처리를 해준다.
visited를 따로 체크해주기 때문에 최종적으로 모든 최단 거리가 담기는 result는 0으로 초기화해주어도 괜찮다.
그러나, visited를 따로 사용하지 않을 것이라면 result를 -1로 초기화하여 방문하지 않았음을 체크해주어야 한다.
❍ BFS
def bfs(x, road):
queue = deque([x])
while queue:
v = queue.popleft()
for i in road[v]:
if not visited[i]:
visited[i] = True
result[i] = result[v] + 1
queue.append(i)
시작 도시를 큐에 담고, 방문 처리되지 않은 도시인 경우를 모두 큐에 담고 방문 처리를 한다.
또한, 현재 도시까지의 거리에서 + 1을 하여 거리를 result에 기록하여 준다.
visited를 사용하지 않고, result를 -1로 초기화한 경우에는 아래와 같이 사용한다.
def bfs(x, road):
queue = deque([x])
while queue:
v = queue.popleft()
for i in road[v]:
if result[i] == -1: # 방문하지 않았다면
result[i] = result[v] + 1
queue.append(i)
❍ CODE
import sys
from collections import deque
input = sys.stdin.readline
# 도시의 개수, 도로의 개수, 거리 정보, 출발 도시의 번호
n, m, k, x = map(int, input().split())
# 도로
road = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
visited[x] = True
for _ in range(m):
a, b = map(int, input().split())
road[a].append(b)
# bfs로 최단 거리 찾기
result = [-1] * (n + 1)
result[x] = 0
# result = [0] * (n + 1)
def bfs(x, road):
queue = deque([x])
while queue:
v = queue.popleft()
for i in road[v]:
if not visited[i]:
visited[i] = True
result[i] = result[v] + 1
queue.append(i)
bfs(x, road)
exist = False
for i in range(1, n + 1):
if result[i] == k:
exist = True
print(i)
if not exist:
print(-1)
❏ 삽질 기록
❍ Issue #1
최단 거리를 알기 위해선 어떻게 해야 할지 고민이 되었다.
예시로 나온 그래프를 직접 DFS와 BFS로 접근해보며, 이미 방문된 노드를 다시 방문하지 않게 되므로 BFS가 최단 거리를 구하는 데에 더 유리하다는 점을 알게 되었다.
❍ Issue #2
이전에 bfs 함수 코드를 참고하여 다음과 같은 코드를 작성했다.
import sys
from collections import deque
input = sys.stdin.readline
# 도시의 개수, 도로의 개수, 거리 정보, 출발 도시의 번호
n, m, k, x = map(int, input().split())
# 도로
road = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
visited[x] = True
for _ in range(m):
a, b = map(int, input().split())
road[a].append(b)
# bfs로 최단 거리 찾기
result = [0] * (n + 1)
def bfs(graph, visited, x):
queue = deque([x])
dist = 0
while queue:
v = queue.popleft()
dist += 1
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
result[i] = dist
bfs(road, visited, x)
exist = False
for i in range(1, n + 1):
if result[i] == k:
exist = True
print(i)
if not exist:
print(-1)
제출하자마자 2%에서 틀렸습니다라는 결과가 떴다. 테스트 코드는 통과했다.
큐에서 pop하여 꺼내온 현재 노드의 dist에서 1을 더하여 계산해주어야 옳게 거리를 측정할 수 있다.
위의 코드대로 하면, 단순히 큐에서 pop하여 꺼내올 때마다 dist가 1씩 증가하므로 옳은 거리를 측정할 수 없다.