[백준] 18352번 : 특정 거리의 도시 찾기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

2. 풀이과정

해당 문제에서 모든 도로의 거리는 1이므로 가중치가 없는 인접 리스트로 그래프를 표현할 수 있다.

인접 리스트(adjacency list)는 파이썬의 리스트를 이용해 그래프를 표현한다.

도시의 개수가 최대 300,000개, 도로의 최대 크기가 1,000,000개이므로 BFS 탐색을 활용해 문제를 시간 복잡도 안에서 해결할 수 있다.

 

주어지는 도로의 정보를 입력받아 인접 리스트로 도시와 도로 데이터의 그래프를 구현한다.

BFS 탐색 알고리즘을 통해 탐색을 수행하며 각 도시로 가는 최단 거리를 저장한다.

탐색 종료 후 시작 도시에서 각 도시로 갈 수 있는 최단 거리가 거리 정보 K와 같은 도시의 번호를 오름차순으로 출력한다.

 

슈도코드

1. N(노드 개수), M(에지 개수), K(목표 거리), X(시작점) 입력받기
2. graph(그래프 데이터 저장 인접 리스트)
3. for M만큼 반복: A(시작점), B(도착점) 입력받아 graph 인접 리스트에 그래프 데이터 저장
4. distance(방문 최단 거리 저장 리스트) -1로 초기화
5. BFS 구현 BFS(v):
   1. queue(큐 자료구조 생성)
   2. queue에 시작 노드 삽입
   3. distance 리스트에 현재 노드 방문 기록 (거리 저장 형태이므로 1 증가)
   4. while (queue가 비어 있을 때까지):
      1. 큐에서 현재 노드 데이터 가져오기
      2. for 현재 노드의 연결 노드 방문:
         1. if 현재 노드의 연결 노드 중 방문하지 않은 노드):
            1. 현재 노드의 distance 리스트 값 1 증가시켜 연결 노드의 distance 리스트 값에 저장
            2. 큐에 연결 노드 삽입
6. BFS(X) 실행
7. if (distance 리스트 값 중 K가 있으면):
   1. for 1 ~ N까지 반복: distance 리스트 값인 방문 거리가 K인 노드의 숫자를 출력
8. else: -1 출력

반응형

3. 소스코드

import sys
from collections import deque

N, M, K, X = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    graph[A].append(B)

distance = [-1] * (N + 1)
def BFS(v):
    queue = deque()
    queue.append(v)
    distance[v] += 1

    while (queue):
        now = queue.popleft()
        for i in graph[now]:
            if (distance[i] == -1):
                distance[i] = distance[now] + 1
                queue.append(i)

BFS(X)

if (K in distance):
    for i in range(1, N + 1):
        if (distance[i] == K):
            print(i)
else:
    print(-1)