[알고리즘/BFS] 18352번 : 특정 거리의 도시 찾기 - python

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

 

 

---

• 문제
• 소요시간: 40분 20초

 

---

• 설계하기(접근방법) 

1. 입력받기

도시를 입력받아 그래프에 넣는다

 

2. 구현하기

q에 넣어서 그래프를 순회한다.

시작시점이 초기화되지 않도록 조건을 걸어준다

 

 

3. 출력하기

오름차순으로 최단거리 도시 목록을 출력한다

 

 

---

• 코드(출력)

from collections import deque
import sys

input = sys.stdin.readline

city, road, distance, start = map(int, input().split())

city_list = []

graph = [[] for _ in range(city + 1)] # [[],[2,3],[3,4],[],[]]
visited = [0 for i in range(city + 1)] # [0,0,0,0,0]


for _ in range(road):
    x, y = map(int, input().split())
    graph[x].append(y)


def bfs(start):
    q = deque()
    q.append(start)
    while q:
        x = q.popleft()
        for i in graph[x]:
            if i != start:
                if visited[i] == 0 or visited[x] + 1 < visited[i]: 
                    visited[i] = visited[x] + 1
                    q.append(i)

bfs(start)

for i in range(len(visited)):
    if visited[i] == distance:
        city_list.append(i)

if city_list:
    for i in city_list:
        print(i)
else:
    print(-1)

---

• 얻어갈 부분

1.bfs가 오랜만이라 많이 해멨다.