[백준] 24445번 알고리즘 수업 - 너비 우선 탐색 2 - python

 

<문제>

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

24445번: 알고리즘 수업 - 너비 우선 탐색 2

<시간 복잡도>

 

<코드>

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

graph = [[] for i in range(n + 1)]
visited = [False] * (n + 1)
cnt = 1
visited_order = [0] * (n+1)
for i in range(m):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
for i in range(len(graph)):
    graph[i].sort(reverse=True)

def bfs(r,visited,cnt,visited_order):
    que = deque()
    que.append(r)
    while que:
        now = que.popleft()
        if not visited[now]:
            visited[now] = True
            visited_order[now] = cnt
            cnt+=1
            for i in range(len(graph[now])):
                que.append(graph[now][i])

    return visited_order

visited_order = bfs(r,visited,cnt,visited_order)
for i in range(1,len(visited_order)):
    print(visited_order[i])

<해설>

이 문제는 지난번에 풀은 bfs의 역으로만 하면된다. 그렇게 어려운 문제는 아니다. 

아래의 문제와 비슷하다 정렬을 역으로만 하면된다.

 

 

https://zoozoozoo.tistory.com/539

[백준] 24444번 알고리즘 수업 - 너비 우선 탐색 1 - python