백준 24444,5번 너비 우선탐색-1,2

너비 우선 탐색문제는 깊이 우선탐색과 다르게 가로로 먼저 움직이는것이다 기준 노드에서 가장 얕은 노드부터 가장 깊은 노드로 탐색 하는 방법이다

너비우선 탐색은 시작점에서 가까운것을 기준으로 탐색하기 때문에 최단경로를 찾을 때 유용하다

 

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

n,m,r = map(int,input().split())
link = [[] for _ in range(n+1)]
ans = [0]*(n+1)
cur = 1
ans[r] = cur #초기정점에 1을 넣음
q = deque([r]) #큐에 탐색의 순서를 넣음

for _ in range(m): #간선 정보 입력
    a,b = map(int,input().split())
    link[a].append(b)
    link[b].append(a)

for lst in link:
    lst.sort()

while q:
    v = q.popleft()
    for i in link[v]:
        if ans[i]:
            continue
        cur += 1
        ans[i] = cur
        q.append(i)

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

 

24445번

위문제와 동일한 문제인데 탐색 방법을 오름차순에서 내림차순으로 변경한게 끝이다

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

n,m,r = map(int,input().split())
link = [[] for _ in range(n+1)]
ans = [0]*(n+1)
cur = 1
ans[r] = cur #초기정점에 1을 넣음
q = deque([r]) #큐에 탐색의 순서를 넣음

for _ in range(m): #간선 정보 입력
    a,b = map(int,input().split())
    link[a].append(b)
    link[b].append(a)

for lst in link:
    lst.sort(reverse=True) #내림차순으로 변경

while q:
    v = q.popleft()
    for i in link[v]:
        if ans[i]:
            continue
        cur += 1
        ans[i] = cur
        q.append(i)

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