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

 

<문제>

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

24444번: 알고리즘 수업 - 너비 우선 탐색 1

<시간 복잡도>

이 문제의 시간 복잡도는 n^2? for 문이랑 while문이 들어가니 그렇게 생각한다

<코드>

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()
    
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 는 dfs 보다 직관적이여서 쉽다. 

우선 이 문제를 풀때는 너비 탐색이므로 deque 를 이용하였다. 

문제를 풀면서 우선 방문 가능한 곳을 다 que 에 넣어주고 하나씩 빼면서 방문 처리하면서 진행하면 된다. 

 

약간 문제를 풀때 함수에 입력하는 값들이 너무 지져분한거 같다.

클린 코드를 짜기위해 노력해야겠다.