99클럽 코테 스터디 5일차 TIL - 백준 2444번 알고리즘수업 너비우선탐색 1 [Python]

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

 

 

 

 

# 학습 키워드

1. BFS (너비우선탐색) 

2. collections.deque : BFS 구현을 위한 deque 자료구조 사용법

3. sys.stdin.readline() : 입력을 짜르게 받기 위한 sys.stdin.readline() 사용법과 rstrip()의 필요성

 

 

 

 

# 문제 접근 방식

주어진 문제는 특정 정점에서 시작하는 너비우선탐색(bfs)을 통해 각 정점을 방문 순서에 따라 번호를 매기는 것이다. 이를 위해 다음과 같은 접근을 사용했다.

 

1. 그래프 입력과 정렬

모든 간선 정보를 입력받아 인접 리스트 형식의 그래프를 생성하고, 탐색에서의 순서를 보장하기 위해 인접 정접을 정렬한다.

 

2. BFS 탐색 

시작 정점에서 bfs를 수행하면서 각 정점의 방문 순서를 기록한다

 

3. 결과 출력

방문 순서를 기록한 리스트를 이용해 각 정점의 방문 순서를 출력한다.

 

 

 

 

# 코드 작성

from collections import deque
import sys
n, m, r = map(int, sys.stdin.readline().rstrip().split())

graph = [[] for _ in range(n+1)]
visited = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())

    graph[a].append(b)
    graph[b].append(a)

for i in range(n+1):
    graph[i].sort()

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = 1
    count = 2

    while queue :
        v = queue.popleft()

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=count
                count += 1

bfs(graph, r, visited)

for i in visited[1::]:
    print(i)

 

 

 

# 회고

이번 코드에서는 bfs의 기본적인 구현 방법을 익히고, 그래프 탐색에서 방문 순서를 기록하는 방법에 대해 공부하였다. 특히 deque를 이용해 bfs의 큐 구현이 효율적으로 이루어졌으며, sys.stdin.readiline()을 통해 입력 속도를 최적화한 것이 주요 학습 포인트이다.

다만, graph 리스트를 정렬하는 과정에서 시간이 추가적으로 소요될 수 있기 때문에, 문제에서 순서가 중요한 경우에만 정렬하는 것이 좋다. 또한, visited 리스트에 방문 순서를 기록하는 과정에서 방문 여부를 숫자로 처리하는 방식에 주의해야 하며, 잘못된 초기화가 발생하지 않도록 유의할 필요가 있다.