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

1. 문제

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

2. 개요

N개의 정점, M개의 간선을 가지는 그래프에서 정점 R부터 BFS를 진행했을 때, 각 정점의 방문 순서를 출력하는 문제. (모든 간선의 가중치는 1이며, 인접 정점은 오름차순으로 방문한다.)

3. 풀이 및 코드

3-1. 풀이

문제에 나온대로 BFS를 진행하면 된다.

한 정점에서 인접 정점을 탐색할 때 먼저 정렬을 수행하여 오름차순 방문이 가능하도록 하고,

방문체크를 할 때는 방문 순서를 1씩 늘려가면서 방문체크를 한다.

3-2. Python

import sys
from collections import deque

N, M, R = map(int, sys.stdin.readline().split())

graph = [[] for i in range(N + 1)]
visited = [0 for i in range(N + 1)]

for i in range(M):
    s, e = map(int, sys.stdin.readline().split())

    graph[s].append(e)
    graph[e].append(s)

q = deque([R])
cnt = 1
visited[R] = cnt

while q:
    now = q.popleft()
    graph[now].sort()

    for nxt in graph[now]:
        if visited[nxt] != 0:
            continue

        cnt += 1
        visited[nxt] = cnt
        q.append(nxt)

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

3-3. C#

namespace boj_24444
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();

            int N = int.Parse(input[0]), M = int.Parse(input[1]), R = int.Parse(input[2]);

            List<int>[] graph = new List<int>[N + 1];
            int[] visited = new int[N + 1];

            for (int i = 0; i < N + 1; i++)
                graph[i] = new();

            for (int i = 0; i < M; i++)
            {
                input = sr.ReadLine().Split();
                int s = int.Parse(input[0]), e = int.Parse(input[1]);

                graph[s].Add(e);
                graph[e].Add(s);
            }

            int cnt = 1;
            Queue<int> q = new();
            q.Enqueue(R);
            visited[R] = cnt;

            while (q.Count > 0)
            {
                int now = q.Dequeue();
                graph[now].Sort();

                foreach (int nxt in graph[now])
                {
                    if (visited[nxt] != 0)
                        continue;

                    visited[nxt] = ++cnt;
                    q.Enqueue(nxt);
                }
            }

            for (int i = 1; i < N + 1; i++)
                sw.WriteLine(visited[i]);

            sw.Close();
        }
    }
}