[백준] 24445번 알고리즘 수업-너비 우선 탐색 2 (BFS 시간 초과 해결)

문제와 입력, 출력

문제 해결 과정

 

입출력

 

이 문제는 단순 BFS 문제였고, 인접 정점을 내림차순으로 정렬하는 조건이 중요했다. 문제가 쉬움에도 불구하고 나는 계속 답은 맞는데 시간 초과 문제가 발생했다. 그 이유는 아래와 같다.

---

시간 초과가 발생했던 이유

 

쓸데 없는 정렬 줄이기!

 

원래 필자는 그래프에 정보를 추가하면서 인접 정점을 정렬하였다. 그래서 정렬 과정이 2번 일어났고 이것이 시간 초과가 발생했던 주된    이유였다. 시간 초과 문제를 해결하기 위해 기존의 정렬 코드를 없애고 그래프 정렬을 위한 for문을 작성하여 정렬과정을 수행했다.

그 결과 정렬 코드의 시간 복잡도가 O(2n)에서 O(n)으로 감소하였다.

---

전체 코드

import sys
from collections import deque

input = sys.stdin.readline
m,n,r = map(int,input().split())
graph = [[] for _ in range(m+1)]

for i in range(n):
    u,v = map(int, input().split())
    graph[u].append(v)
    # graph[u].sort(reverse=True)
    graph[v].append(u)
    # graph[v].sort(reverse=True)

[graph[i].sort(reverse=True) for i in range(1,m+1)]

def bfs(graph, i, visited,ans):
    queue = deque([i])
    visited[i] = True
    cnt = 0
    while queue:
        cnt += 1
        v = queue.popleft()
        ans[v] = cnt

        for r in graph[v]:
            if not visited[r]:
                queue.append(r)
                visited[r] = True
    
visited = [False] * (m+1)
ans = [0] * (m+1)
bfs(graph,r,visited,ans)
[print(ans[k]) for k in range(1,m+1)]

---

한 줄 요약

그래프를 정렬할 때는 O(n)의 시간 복잡도가 나오도록 코딩하자!