백준 18352 문제 링크: https://www.acmicpc.net/problem/18352
📑 문제 설명
num of vertex: 1~N
num of edge: M
k: 거리
시작점이 주어졌을 때 시작점으로부터 k만큼의 거리 이동으로 도착할 수 있는 도시를 찾고 해당 도시를 오름차순으로 출력하기
--> 동일한 가중치를 갖으면서 방향성이 있는 그래프: Directed Graph
입력
- 첫째줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시 번호 X
- 둘째줄부터 M개의 도로 개수에 걸쳐 두 개의 자연수 A, B가 공백을 기준으로 구분되어 입력
- A, B: A에서 B로 가는 도로가 존재한다
출력
- X로부터 출발하여 도달할 수 있는 도시 중에서 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력
- 없는 경우 -1 출력
💡 문제 해결 방법
알고리즘: BFS
이유: 시작점으로부터 최단 거리 K만큼 떨어진 도시들을 찾아야 하기 때문에
예외처리
- 없는 경우 -1을 출력한다
💻 코드
from collections import deque
import sys
# 입력
# n, m, k, s = map(int, input().split())
n, m, k, s = list(map(int, sys.stdin.readline().split()))
graph = {}
for i in range(n+1):
graph[i] = []
for i in range(m):
a, b = list(map(int, sys.stdin.readline().split()))
graph[a].append(b)
# bfs
dist_list = [0 for _ in range(n + 1)]
visited = [0 for _ in range(n+1)]
queue = deque([s])
# queue.append(s)
visited[s] = 1
while (queue):
now = queue.popleft()
for j in graph[now]:
if visited[j] == 0:
queue.append(j)
visited[j] = 1
dist_list[j] = dist_list[now] + 1
check = 0
for i in range(1, n+1):
if dist_list[i] == k:
print(i)
check += 1
if check == 0:
print(-1)
💟 추가적으로 알게 된 점
- 예시 답변부터 반례까지 다 입력했을 때 정답임에도 불구하고 "틀렸습니다"가 나왔다. 그 이유는 내가 생각하기에 시간을 단축시키고자 거리가 1인 경우에는 bfs 넣지말고 바로 출력하는 if 문을 추가해서 그랬었다. 참나.. 그거 빼니까 잘 돌아감 ㅠㅠ
- 파이썬 입력 시 input() 보다는 sys.stdin.readline() 이거로 받아야 시간이 덜 걸린다고 한다. sys.stdin.readline()을 사용하려고 노력하자
