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

문제 요약

• 알고리즘 분류: bfs
• 난이도:Silver2
• 문제내용:
  • 넓이 우선 탐색후 각 노드 마다 방문 순서(오름차순)를 출력해라

• 사이트: https://www.acmicpc.net/problem/24444

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

문제풀이

 이번 문제는 BFS 탐색 문제이다.  BFS 탐색 알고리즘에 관한 자세한 설명은 여기에서 확인 해보면 알 수 있다.

여기 bfs에 추가되는 요건은 2가지이다. 

1. 오름차순 정렬
2. 방문순서

 1번은 그래프를 만든후 각 노드에서 연결 된 노드를 오름차순으로 정렬 하면되고 2번은 count변수를 선언한후 방문 할때마다 count를 늘려서 방문한 노드에  count를 넣으면된다. bfs알고리즘만 알면 구현은 간단해서 따로 설명은 안하겠다.

 

Code

Python

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

def bfs(start_node):
    global count
    visited[start_node] = count
    count += 1
    queue = deque([start_node])
    while queue:
        node = queue.popleft()
        for n in grape[node]:
            if visited[n] == 0:
                visited[n] = count
                count += 1
                queue.append(n)

N, M, start = map(int, input().split())
grape = {i : [] for i in range(1, N + 1)}

for _ in range(M):
    a, b = map(int, input().split())
    grape[a].append(b)
    grape[b].append(a)

visited = [0] * (N + 1)

for i in range(1, N + 1):
    grape[i].sort()

count = 1
bfs(start)
print('\n'.join(map(str, visited[1:])))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static Map<Integer, ArrayList<Integer>> grape = new HashMap<Integer, ArrayList<Integer>>();
	static int N;
	static int[] visited;
	static int count = 1;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(st.nextToken());
		
		for(int i = 1; i <= N; i++) {
			grape.put(i, new ArrayList<Integer>());
		}
		visited = new int[N + 1];
		
		int a, b;
		for(int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			grape.get(a).add(b);
			grape.get(b).add(a);
		}
		
		for(int i = 1; i <= N; i++) {
			Collections.sort(grape.get(i));
		}
		bfs(start);
		StringBuilder sb = new StringBuilder();
		for(int i = 1; i <= N; i++) {
			sb.append(visited[i]).append("\n");
		}
		System.out.println(sb);
		
	}
	
	public static void bfs(int strat_node) {
		visited[strat_node] = count;
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(strat_node);
		int node;
		while(!queue.isEmpty()) {
			node = queue.poll();
			for(int n : grape.get(node)) {
				if(visited[n] == 0) {
					visited[n] = ++count;
					queue.add(n);
				}
			}
		}
	}

}