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

문제

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

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

 

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

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

 

---

풀이

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

# BFS로 노드를 방문할 경우 노드의 방문 순서 출력해라
# 방문한 순서로 정점 번호를 출력하는 것이 아니라 🌟 정점 순서로 방문한 순서를 출력해야 합니다.
# -> 오름차순 노드(정점)별 ex_1, 2, 3, 4, 5 방문한 순서를 출력하기

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

# 정점의 수, 간선의 수, 시작 정점
N, M, R = map(int, input().split(' '))

queue = deque()

visited = [0] * (N+1)

graph = [[] for _ in range(N+1)]

for i in range(M):
    a, b = map(int, input().split(' '))
    graph[a].append(b)
    graph[b].append(a)

for i in graph:
    i.sort()

def bfs(v):
    queue.append(v)
    cnt = 1
    visited[v] = 1

    while queue:
        u = queue.popleft()

        for ele in graph[u]:
            if visited[ele] == 0: # 방문하지 않았다면
                cnt += 1 # 방문 순서 증가
                queue.append(ele)
                visited[ele] = cnt # 방문 순서 기록

bfs(R)

for i in range(1, len(visited)):
    print(visited[i])

아이디어

• 간선의 수 M만큼 for문으로 양방향 인접 리스트를 만들어준다.
• 양방향 인접 리스트의 각 리스트를 오름차순으로 정렬해준다.
• visited에 방문 순서를 기록해주고, 마지막에 처음 노드부터 방문 순서를 한 줄씩 출력해준다.

bfs 순서대로 잘 방문하는 것 같은데 계속 틀려서 질문 게시판을 보니 '방문한 순서로 정점 번호를 출력하는 것이 아니라 정점 순서로 방문한 순서를 출력해야 합니다.' 라는 힌트를 얻고 다시 풀었다.

문제에서 '정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.' 이 부분을 보고 정점 순서로 방문한 순서를 출력해야 한다는 점을 파악했어야 했다.

 

---

 

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

import sys
from collections import deque

input = sys.stdin.readline

N, M, R = map(int, input().split(' '))

graph = [[] for _ in range(N+1)]

visited = [0] * (N+1)

queue = deque()

for i in range(M):
    a, b = map(int, input().split(' '))
    graph[a].append(b)
    graph[b].append(a)

for i in graph:
    i.sort(reverse=True)

def bfs(v):
    queue.append(v)
    cnt = 1
    visited[v] = 1

    while queue:
        u = queue.popleft()

        for ele in graph[u]:
            if visited[ele] == 0:
                cnt += 1
                visited[ele] = cnt
                queue.append(ele)

bfs(R)

for i in range(1, len(visited)):
    print(visited[i])

아이디어

• 양방향 인접 리스트의 각 리스트를 내림차순으로 정렬(탐색)하는 것 외에 1과 풀이가 동일하다.

 

시간 복잡도

그래프를 인접 리스트로 표현하는 데에는 O(간선의 수_M)의 시간이 소요.
정렬 -  O(nlogn) -> O(M * nlogn) 
BFS 수행 시간 - O(정점의 개수 + 간선의 개수) => O(N + M)
전체 - O(M + N + M + M*NlogN)

공간 복잡도

O(N+M)

 

---

 

🙂 공부하면서 정리하는 글입니다. 잘못된 점이 있다면 피드백 남겨주시면 감사합니다.