[BOJ] 18352번 특정 거리의 도시 찾기 / 사용언어 : 파이썬(python)

※ 문제링크

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

해당 문제는 BFS를 사용해서 풀 수 있는 문제였다. 문제분류는 다익스트라 알고리즘으로 분류되어 있으나 BFS만 사용할 줄 알아도 풀 수 있는 문제였다. 풀이방법을 간단하게 이야기하면 입력값을 바탕으로 딕셔너리를 사용해서 그래프를 구현한 후, 반복문을 통해 간선으로 이어진 도시들을 방문하면서 방문여부를 체크하고, 요구받은 거리값까지 반복문을  돌렸을때 남는 값을 출력하면 된다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값을 딕셔너리를 활용하여 그래프로 구현한다. 단방향이므로 출발도시와 도착도시만 가지고 그래프를 구현해야한다.

2. 양방향 간선으로 이어지지 않은 정점의 경우, 반복문을 통해 그래프를 구현한 딕셔너리에 빈 리스트값으로 부여해준다.

3. BFS를 deque를 이용해서 구현하고, 반복문을 통해 한번에 이동할 수 있는 도시들을 확인할 수 있게 구현한다.

4. K값(이동거리)만큼 반복문을 통해 BFS함수를 돌리고 조건에 만족하는 값들을 queue에 추가한다.

5. queue가 비어있을 경우 -1을 추가해주고, 출력전 sort를 사용해서 오름차순으로 정렬해준다(필수)

6. sys함수를 사용하여 결과값을 출력해준다.(개행문자에 유의하여 출력해야한다.)

 

from collections import deque
import sys 

N, M, K, X = map(int, input().split())
graph = dict()
for i in range(M):
    city_s, city_e = map(int, input().split())
    if city_s not in graph:
        graph[city_s] = [city_e]
    else:
        graph[city_s].append(city_e)

for i in range(1, N+1):
    if i not in graph:
        graph[i] = []
        
visited = [False for _ in range(N+1)]

def bfs(queue):
    cities = []
    for _ in range(len(queue)):
        city = queue.popleft()
        if visited[city] == False:
            visited[city] = True
            queue.extend(graph[city])
            cities.append(city)
    return cities

queue = deque()
queue.extend(graph[X])
visited[X] = True
for _ in range(K):
    ans = bfs(queue)
if len(ans) == 0:
    ans.append(-1)
for i in range(len(ans)):
    if i == len(ans) - 1:
        sys.stdout.write(f'{ans[i]}')
    else:
        sys.stdout.write(f'{ans[i]}\n')

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.