[Python] 18352번 특정 거리의 도시 찾기

✏️ 문제

 

문제 파악

예전 트리 부모 찾기  문제랑 비슷한 맥락이다.

인접리스트를 사용해서 풀었고 BFS를 활용했다. 

 

해당 도시까지 가는 거리가 거리 정보 k와 같다는 조건문을 어디다가 둬야할 지 조금 헤맸다. 

visited 1차원 배열에 처음 넣은 도시에서 다른 도시까지의 거리를 +1씩 하며 이 거리가 k와 같으면 해당 visited 배열의 인덱스를 출력하는 방식으로 코드를 짰다.

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 데이크스트라
• 최단 경로

 

 

코드

from collections import deque
import sys
input = sys.stdin.readline

n, m, k, x = map(int, input().split())
graph = [[] * (n+1) for _ in range(n+1)]
visited = [300001] * (n+1)
cities = []

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

def bfs(x):
  q = deque([x])
  visited[x] = 0
  cities = []

  while q:
    node = q.popleft()
    
    if visited[node] == k: 
      cities.append(node)

    for neighbor in graph[node] :
      if visited[neighbor] == 300001:
        q.append(neighbor)
        visited[neighbor] = visited[node]+1

  if len(cities) == 0:
    cities.append(-1)
  return cities

cities = bfs(x)
cities.sort()
for city in cities:
  print(city)

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS