백준 알고리즘 18352: 특정 거리의 도시 찾기(Python)

https://www.acmicpc.net/problem/18352

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

문제 

---

문제 해결을 위한 과정

이 문제의 경우 BFS를 통해서 쉽게 해결할 수 있는 문제였습니다. 정답률은 32퍼센트로 좀 낮은 편인데 난이도에 비해서는 정답률이 조금 낮게 나온 것 같습니다. BFS라는 개념을 정확히 알면 쉬운 문제입니다. 만일 BFS를 잘 모르시겠다면 https://bgspro.tistory.com/15?category=981927

BFS 너비 우선탐색 (Python)

한번 보고 오시는걸 추천드립니다. 예시의 그림을 보면 노드가 양방향으로 연결이 된 것이 아닌 단방향으로 연결이 되어있는 것을 확인할 수 있습니다.  시작 지점부터 BFS방식을 통해 탐색을 해 나아가면 예시의 그림을 예로 들면 첫 번째로 탐색이 되는 2, 3 그리고 두 번째로 탐색이 되는 4를 통해 몇 번째로 탐색이 되느냐가 시작 지점 노드 1부터 얼마만큼의 거리가 떨어져 있는지를 의미하는 것이라고 보면 되겠습니다. 따라서 몇 번째로 탐색이 되는지 확인을 한 뒤 입력받은 k와 같다면 어떠한 리스트에 추가를 한 뒤 오름차순으로 정렬을 하면 되는 문제였습니다.

---

소스코드 

import sys
from collections import deque
# 입력을 빠르게 하기 위함 이 방식이 아닌 일반 input일 경우 pypy3는 통과하지만 python3로는 통과하지 못함
input = sys.stdin.readline 
 
N, M, K, X = map(int, input().split())
graph = [[] for _ in range(1 + N)]
visited = [False] * (1 + N)
answer = []
 
for i in range(M):
  a, b = map(int, input().split())
  graph[a].append(b)
 
def bfs(graph, x, visited):
  queue = deque([x])
  visited[x] = True
  count = 1
  while queue:
    for _ in range(len(queue)): # 몇번째로 탐색이 되는지 확인하기 위한 for문
      v = queue.popleft()
      for i in graph[v]:
        if not visited[i] and count == K: # 방문하지 않고 K와 ㅏㅌ은 경우
          answer.append(i)
        if not visited[i]: # 방문하지 않은 경우
          visited[i] = True
          queue.append(i)
    count += 1
 
bfs(graph, X, visited)
answer.sort() # 오름차순으로 
 
if len(answer) != 0:
  for data in answer:
    print(data)
else:
  print(-1)