백준 18352 파이썬 BFS탐색 알고리즘

2024. 6. 4. 06:18코딩 도구/백준

반응형

백준 18352 - 특정 거리의 도시 찾기

문제

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

 

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

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개

www.acmicpc.net

18352

답안 코드 :

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

N, M, K, X = map(int, input().split())  # 노드의 수, 에지의 수, 목표거리, 시작점
A = [[] for _ in range(N + 1)]
answer = []
visited = [-1] * (N + 1)

def BFS(v):  # BFS 탐색 함수 구현
    queue = deque()
    queue.append(v)
    visited[v] += 1
    while queue:
        now_Node = queue.popleft()
        for i in A[now_Node]:
            if visited[i] == -1:
                visited[i] = visited[now_Node] + 1
                queue.append(i)

for _ in range(M):
    S, E = map(int, input().split())
    A[S].append(E)

BFS(X)

for i in range(N + 1):
    if visited[i] == K:
        answer.append(i)
if not answer:
    print(-1)
else:
    answer.sort()
    for i in answer:
        print(i)

생각 :

# 문제 분석
# 모든 도로의 거리가 1이라서 가중치가 없는 인접 리스트로 표현
# 도시 300,000 , 도로 최대 크기 1,000,000이므로 BFS탐색사용하면 해결 가능

# 문제 풀이
# 인접 리스트로 도시, 도로 그래프 구현
# BFS탐색 알고리즘으로 탐색하면서 각 최단 거릿값을 방문 리스트에 저장
# 탐색 종료 후 방문 리스트에서 값이 K와 같은 도시 번호를 출력

 

그래프 표현 참고자료 블로그

https://mkisos.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%98-%ED%91%9C%ED%98%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0

 

그래프의 표현 (알고리즘, 자료구조)

그래프에 대해서 그래프는 노드와 에지로 구성된 집합이다. 노드는 데이터를 표현하는 단위이고 에지는 그 노드들을 연결한다. 그래프는 여러 알고리즘에 많이 사용되는 자료구조이므로 코딩

mkisos.tistory.com

 

반응형