[BOJ_Python] 24444. 알고리즘 수업 - 너비 우선 탐색 1

문제

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

 

사용 알고리즘

BFS

 

풀이

고려사항

1. 양방향 그래프

2. 각 노드에서 다음 갈 수 있는 노드 오름차순으로 방문

 

후기

1. 가장 기본적인 BFS 알고리즘에 정렬만 들어간 문제이다.

2. 그래프를 만들때 인덱스가 헷갈리지 않게 V+1으로 초기 세팅하여 각 수와 인덱스 번호를 맞췄다.

3. deque와 visited를 활용하여 기본 BFS를 진행하였다.

 

코드

import sys
from collections import deque

input = sys.stdin.readline

V, E, S = map(int, input().split())
gp = [[] for _ in range(V + 1)]

# 그래프 초기 세팅
for _ in range(E):
    start, end = map(int, input().split())
    gp[start].append(end)
    gp[end].append(start)

# 각 노드 별 다음 노드 정렬
for _ in range(V + 1):
    gp[_].sort()

q = deque([S])
visited = [0 for _ in range(V + 1)]
visited[S] = 1
cnt = 1

while q:
    cur = q.popleft()
	
    # 해당 노드에서 갈 수 있는 노드 확인
    for next in gp[cur]:
        # 아직 방문하지 않은 곳만 방문
        if visited[next] == 0:
            cnt += 1
            visited[next] = cnt
            q.append(next)

for i in range(1, V + 1):
    print(visited[i])

 

결과