[Baekjoon]백준 24445 알고리즘 수업 - 너비 우선 탐색 2(실버 2) - Python

문제설명 1

문제설명 2

문제를 살펴보면 이전 문제처럼 너비 우선 탐색으로 해결을 하되, 이번에는 인접 정점을 내림차순으로 방문한다

따라서 이전 코드를 그대로 사용하되, sort()를 sort(reverse=True)로 바꾸어 사용하면 정답을 확인할 수 있다

이전문제 블로그 링크 : https://reflesh02.tistory.com/168

[Baekjoon]백준 24444 알고리즘 수업 - 너비 우선 탐색 1(실버 2) - Python

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

def bfs(start):
    global cnt
    queue = deque([start])
    visited[start] = cnt

    while queue:
        cur = queue.popleft()
        for neighbor in graph[cur]:
            if visited[neighbor] == 0:
                cnt += 1
                visited[neighbor] = cnt
                queue.append(neighbor)

vertex, edge, starting = map(int, input().split())
graph = [[] for _ in range(vertex+1)]
visited = [0] * (vertex+1)
cnt = 1

for _ in range(edge):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    
for g in graph:
    g.sort(reverse=True)
    
bfs(starting)

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