백준 24444 알고리즘 수업-너비 우선 탐색1 (BFS 기초 - 2차원배열)

BFS 다시 정리할 겸 기본문제를 풀어보았다.

- 알아야 할 점

1. 주어진 문제가 양방향인지 단방향인지 판단해야 한다. 양방 일 경우, append를 두 노드 다 해야한다.
   
   
2. 2차원에 관한 문제일 경우 노드에 연결된 다른 노드를 저장시키는 배열이 필요하다. (예를들어, 1번 노드와 3,4번이 연결될 경우 -> lis[1] = [3,4])
   
   
3. BFS는 보통 deque를 이용해 popleft (최상단) 노드를 꺼내며 연결되어있는 노드를 탐색하는 식으로 진행된다.
   
   
4. 방문 배열 visit를 만들어야 중복이 없이 경우의 수를 구할 수 있다. visit[i] = 0라면 해당 노드는 방문해야한다. 또한, visit[i] = 정수로 저장한다면 정수는 해당 노드의 방문횟수이다.

해당 그림과 같이 연결된다. 코드를 아래와 같이 나타낼 수 있다. 반드시 sort를 해줘야 탐색이 안꼬인다.

from collections import deque

def bfs(lis, start, visit):
    que = deque([start])
    visit[start] = 1
    cnt = 2

    while que:
        top = que.popleft()

        for i in lis[top]:      # 최상단 노드에 대한 연결된 노드
            if not visit[i]:    # 연결된 i가 방문되지 않았다면
                que.append(i)
                visit[i] = cnt      #visit에 방문 횟수를 넣음
                cnt += 1        # cnt

n, m, r = map(int, input().split())
lis = [[] for _ in range(n+1)]
visit = [0] * (n+1)

for i in range(m):
    a, b = map(int, input().split())

    lis[a].append(b)
    lis[b].append(a)        # 양방향간선

for i in range(n+1):
    lis[i].sort()       # 배열 정렬 필요

bfs(lis, r, visit)

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