99클럽 코테 스터디 5일차 TIL : 백준 24444번, 너비우선탐색

 

1. 오늘의 문제

 

오늘은 어제에 이어 너비우선탐색, BFS였다. 

 

어제 깊이 우선탐색을 했으니 조금만 바꾸면 되겠지? 싶었지만...

 

시간초과가 자꾸 걸렸다.

 

오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.

너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.

 

2. 원리

 

깊이우선탐색에선 stack을 이용했는데, 너비우선탐색에선 que를 이용했다.

 

문제는 que에서 제일 앞에있는걸 빼는 것이었다.

 

pop()을 이용했더니 리스트 전체의 인덱스를 변경하는데 O(n)의 시간이 소요됬다.

 

그래서 deque를 이용해서 문제를 해결함.

 

다음에 시간나면 deque를 한번 파이썬으로 구현해보고 싶다.

 

3. 코드

 

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

# 노드 수, 간선의 수, 시작 숫자를 입력 받음
v, e, s = map(int, put().split())

# 방문 여부를 표시하기 위한 리스트와 각 연결을 확인하기 위한 리스트를 만듦
visited = [0 for x in range(v+1)]
line = [[] for x in range(v+1)]

# 노드의 수만큼 for문을 돌면서 입력 받음.
# 입력 받은 자료에서 연결을 각각의 리스트에 저장
for i in range(e):
    n, f = map(int, put().split())
    line[n].append(f)
    line[f].append(n)
    
# 리스트를 정렬함
for l in line:
    l.sort()
    
# 검색을 위한 큐. 일단 시작 숫자를 넣어줌
# order는 방문 횟수를 기록하기 위함
que = deque()
que.append(s)
order = 0

while que:
    target = que.popleft()
    if visited[target] != 0:
        continue
    order += 1
    visited[target]=order
    # 해당 노드를 전개해서 큐에 집어넣는다.
    for node in line[target]:
        que.append(node)
    
# visited에 내용을 출력한다.
for v in visited[1:]:
    print(v)

 

4. 느낀점

 

아직 배워야 할 것이 많다는 걸 느꼈다.

 

코딩 교육을 제대로 받아본 적이 별로 없는데, 이번 기회를 통해서 많이 배우는 것 같아 기분이 좋다.