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

✏️ 문제

 

문제 파악

예전 트리 부모 찾기  문제랑 비슷한 맥락이다.

인접리스트를 사용해서 풀었고 BFS를 활용했다. 

 

개수가 아닌 순서이므로 들렸으면 +1 씩 해줘야 한다. 그래서 인접리스트의 한 배열을 방문한 후에 순서를 +1 하도록 코드를 짰다.

그리고 문제에서 오름차순으로 방문한다고 했으므로 인접리스트의 한 배열을 방문하기 전에 인접리스트를 오름차순하고 돌아가도록 코드를 구성했다.

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 정렬

 

 

코드

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

n, m, r = map(int, input().split())
graph = [[] * (n+1) for _ in range(n+1)]
visited = [0] * (n+1)

for _ in range(m):
  u, v = map(int, input().split())
  graph[u].append(v)
  graph[v].append(u)

def bfs(x):
  order = 1
  q = deque([x])
  visited[x] = order
  
  while q:
    node = q.popleft()
    graph[node].sort()

    for neighbor in graph[node]:
      if visited[neighbor] == 0: 
        order += 1
        visited[neighbor] = order
        q.append(neighbor)

bfs(r)
for i in range(n):
  print(visited[i+1])

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS