[JAVA 자바] 백준 24479번 : 너비 우선 탐색 1

▶ 문제

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

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

 

▶ 설명

그래프 탐색 알고리즘에는 DFS와  BFS가 있다.

 

BFS는 Breadth First Search(너비 우선 탐색)의 약자로, 노드를 탐색하는 방향이 넓게 가고, Queue 자료구조가 사용된다.

DFS 는  Depth First Search(깊이 우선 탐색)의 약자로, 노드를 탐색하는 방향이 넓게 가는 것이 아니라 깊숙이 들어간다는 특징이 있고, Stack 의 자료구조가 녹아져 있다. 그러나 실제 코드에서는 stack 이 아닌 재귀함수로 구현된다.

 

문제 살펴보기

예제를 통해 문제를 다뤄보려고 한다.

간선으로 연결된 두 노드가 입력된다.

이를 그래프로 그려보면 다음과 같다.

 

DFS 였다면 1에서 출발한다고 했을 때 1과 연결된 2, 4 중 작은 수인 노드 2를 탐색하고,

노드 2와 연결된 1, 3, 4 중에서 방문했던 1을 제외하고 3, 4 중 가장 작은 수인 노드 3을 탐색하는 식으로 방문이 진행될 것이다.

하지만 BFS의 경우는 1에서 출발한다고 했을 때 1과 연결된 2, 4 를 순서대로 탐색한다.

2부터 또 연결된 1, 3, 4 중 방문을 하지 않은 3을 탐색하고,

노드 4와 연결된 1, 2, 3 중에서 방문하지 않은 노드를 탐색하면 된다. (노드 4와 연결된 노드들 중 방문하지 않은 노드는 없으므로 탐색이 종료된다.)

탐색 과정을 살펴보면 같은 degree 선상에 있는 모든 노드를 탐색한 후 다음 degree로 넘어가 탐색하는 것을 알 수 있다.

마치 아파트 택배처럼 같은 층에 있는 집끼리 묶어서 층을 오고가며 배달하는 것 과 같다고 볼 수 있다.

 

 

연결된 노드들

노드 1은 2, 4 노드와 연결되어 있는 것처럼 다른 노드들도 2차원 배열로 나타내면 아래와 같다.

 

array = [

       [],

       [4, 2],

       [1, 3, 4],

       [2, 4],

       [1, 2, 3],

       [],

]

 

편하게 배열에 접근하기 위해 인덱스 0은 비워두고 1부터 노드 1로 보도록 하면된다.

이러한 배열은 중첩된 ArrayList로 구현하는 것이 편하다. 배열의 크기를 처음부터 알지 못하기 때문이다.

중첩 ArrayList를 만들게 되면 배열로 된 ArrayList 객체를 또 여러개의 ArrayList로 묶는 형태가 된다.

 

문제에서 오름차순으로 방문한다고 했으므로 배열 안의 원소배열들을 각각 오름차순 정렬해준다.

 

array = [

       [],

       [2, 4],

       [1, 3, 4],

       [2, 4],

       [1, 2, 3],

       [],

]

 

(코드 구현)

이제 위의 나열된 것들을 가지고 노드 방문을 할 수가 있다.

문제에서의 예제는 다른식으로 그래프를 알려주고 있으므로 위 같은 배열로 만들어주는 작업을 거쳐야 한다.

첫 입력은 1, 4 였다. 노드1에 4를 추가하고, 노드 4에 1을 추가하면 된다.

 

탐색 순서

노드 1에서 시작한다고 했을 때 Queue에 1을 저장한다. (queue : 1)

 

그리고 노드 1과 연결된 2, 4 노드를 모두 방문처리하고,

1을 queue에서 빼냄과 동시에 2, 4를 차례로 저장시킨다. 물론 방문처리 하지 않은 노드들만 저장한다.(queue : 2, 4)

 

queue에서 front부터 숫자를 꺼내면서 그 노드와 연관된 노드들을 탐색하는 순서로 되어 있다.

노드 2와 연결된 1, 3, 4 중에서 방문하지 않은 3을 back 에 넣고, 노드2를 Queue에서 빼낸다. (queue : 4, 3)

 

queue의 front에 있는 노드 4와 연관된 노드를 탐색해보고 모두 방문한 노드라면 아무 작업 없이 (back에 넣을 숫자는 없음을 의미) 4만 queue에서 빼온다. (queue : 3)

 

3도 마찬가지로 처리한다. (3과 연결된 노드들이 모두 방문한 노드였으므로 그냥 3만 빼온다. (queue: 비어있음)

 

여기서 알아야할 점은 queue에 노드 번호를 넣고 빼는 것을 반복하면서 queue가 비어있으면 노드를 모두 탐색했다고 보는 것이다.

 

 

 

 

 

🌱 풀이

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

public class Main {
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
	static int check[];
	static int cnt;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());

		check = new int[n + 1];

		for (int i = 0; i < n + 1; i++) {
			graph.add(new ArrayList<Integer>());
		}

		// 리스트에 노드와 연결된 노드번호들을 저장하기
		while (m-- > 0) {
			st = new StringTokenizer(br.readLine(), " ");
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());

			graph.get(u).add(v);
			graph.get(v).add(u);
		}

		// 오름차순 정렬
		for (int i = 1; i < graph.size(); i++) {
			Collections.sort(graph.get(i));
		}

		cnt = 1;
		bfs(r);

		for (int i = 1; i < check.length; i++) {
			sb.append(check[i]).append("\n");
		}
		System.out.println(sb);

	}

	private static void bfs(int node) {
		check[node] = cnt;
		LinkedList<Integer> q = new LinkedList<>();
		q.offer(node);
		
		while (!q.isEmpty()) {
			int num = q.poll();
			for (int i = 0; i < graph.get(num).size(); i++) {
				int newNode = graph.get(num).get(i);
				if (check[newNode] == 0) {
					cnt++;
					check[newNode] = cnt;
					q.offer(newNode);
				}
			}
		}
	}
}

 

---

(코드 관련 풀이는 DFS 1 문제에서 이미 다뤘던 내용과 유사하므로 

다루지 않은 부분만 설명하려고 한다.)

 

dfs 함수는 재귀로 되어있는 반면, bfs 함수는 정확히 queue 자료구조를 활용하였다.

LinkedList 로 queue를 만들어 방문하고 있는 노드를 queue 에 넣도록 한다.

queue 안에 데이터가 없을 때까지 반복문을 실행하도록 하고,

방문한 노드를 빼고(poll()), 그 방문한 노드에서 방문한적이 없는 노드들을 탐색하여서 queue에 저장하도록 한다. 1개가 될 수 있고, 여러개가 저장될 수가 있다. 

queue 안에 데이터가 모두 poll() 되어서 없다면 탐색을 종료하도록 한다.

 

 

 

▶ Log