[DFS/BFS] 백준 18352번: 특정 거리의 도시 찾기 Silver II (Python 파이썬) ⭐

💡문제 링크

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

 

💡문제 분석 요약

N개의 노드가 M개의 간선으로 이어져 있다. X노드에서 시작해서 간선 K개를 지나 도달할 수 있는 노드를 모두 출력하는 문제

즉 최단거리가 K인 모든 노드를 출력하는 문제(한 줄에 하나씩, 오름차순으로)최단거리가 K인 노드가 없으면 -1을 출력한다

💡알고리즘 설계

1. n, m, x, k를 입력받는다.

2. 입력받은 간선정보를 graph 리스트에 넣는다.

3. 큐 자료구조에 x를 넣는다.

4. 큐 자료구조에서 제일 왼쪽에 있는 원소를 빼낸다(선입선출)

5. graph[x]에 속한 원소들, 즉 x노드에서 간선 하나로 이동할 수 있는 노드들에 대해 아직 방문 안 한 노드면 방문처리하고, 이동거리를 계산한다. 

6. 큐 자료구조에 아무것도 남은 게 없을 때까지 4, 5를 계속 반복한다.

7. 반복이 끝난 후, distance리스트에서 k인 원소의 인덱스들을 출력한다(만약 k인 원소가 없으면 -1 출력)

 

💡코드

# 필요한 라이브러리 불러오기
from collections import deque
import sys
input = sys.stdin.readline

# 입력값 받아오기
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]
distance = [0] * (n+1) # i번째 원소는 x노드에서 i노드까지의 최소거리
visited = [False] * (n+1) # 방문처리하는 리스트

for _ in range(m): # graph를 만드는 반복문
    a, b = map(int, input().split())
    graph[a].append(b) 

# BFS 함수
def bfs(graph, x, visited):
    visited[x] = True
    queue = deque([x])
    
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
                distance[i] = distance[v] + 1 # v에서 i노드로 이동하였으므로 이동거리 계산
    
    if k not in distance: # 최소거리가 k인 노드가 없을 경우
        print(-1)
    else: 
        for j in range(len(distance)): # 최소거리가 k인 노드를 오름차순으로 출력
            if distance[j] == k:
                print(j)
                
bfs(graph, x, visited)

 

💡 오답 풀이

1. 처음에 DFS로 풀려고 했는데 잘 안 풀렸다.. 최소거리가 정해져있으므로 DFS(Depth First Search, 깊이 우선 탐색) 대신 BFS(Breath First Search, 너비 우선 탐색)으로 풀어야 한다.

2. 이동거리가 k로 정해져있는데, 이걸 어떻게 코드로 처리해야하나 고민이 많았다. 결국 거리정보를 저장하는 distance 리스트를 새로 만들었고, distance[i] = distance[v] + 1 코드를 통해 이동거리를 계산했다.

3. 최소거리가 k인 노드가 없을 경우 -1을 출력해야하는데, 이 조건을 까먹어서 틀렸다.

4. sys.stdin.readline()을 안 했더니 런타임에러가 자꾸 떴다..

import sys
input = sys.stdin.readline
코드에서 input().split()

이거 3개 기억하자!

💡 다른 풀이

distance에서 k인 원소의 인덱스를 출력하는 코드인데,원소가 k일 경우 answer 리스트에 넣고 answer를 정렬해서 출력하는 다른 풀이도 있었음.하지만 distance 원소의 인덱스 = 노드 번호이므로, 굳이 정렬할 필요도 없어서 나는 인덱스 출력하는 코드로 했다!

 

💡 느낀점 or 기억할정보

1. 어렵다..

2. 이동거리가 정해져있는 경우 이동거리정보를 기억하는 리스트 distance = [0] * (n+1)를 만들고 시작하자!

3. deque 쓰려면 from collections import deque 해야한다.