[JAVA 자바] 백준 24479번 : 깊이 우선 탐색 1

▶ 문제

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

 

▶ 설명

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

 

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

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

 

문제 살펴보기

이 문제에서는 간선으로 연결된 노드가 두 개씩 입력된다.

 

 

이 문제의 예제에서 입력된 값으로 그래프를 그려보면 다음과 같다.

 

 

 

연결된 노드들

그리고, 위의 그래프를 바탕으로 각 노드마다 연결된 노드를 나열하면 다음과 같다.

 

노드1 : 4, 2

노드2 : 1, 3, 4

노드3 : 2, 4

노드4 : 1, 2, 3

노드5 : x (연결된 노드 없음)

 

(코드 구현)

그럼 코드로 연결지어 어떻게 구현하면 될지 살펴보자.

첫 입력은 1, 4 였다.

노드1에 4를 추가하고, 노드4에 1을 추가하면 된다.

2차 배열로 만들어야 하지만 추가했을 때 총 배열의 길이는 처음에 예측할 수 없으므로

배열이 아닌 ArrayList를 중첩하여 구현하도록 한다.

 

탐색 순서

(순서1) 노드 1에서 시작했을 때

노드 1과 연결된 2,4의 노드 중 작은 숫자로 된 노드2를 탐색한다.(순서2) 

 

노드2에서 연결된 1, 3, 4 노드 중에서 작은 숫자인 노드 1을 탐색 하여야 하지만 이미 탐색했던 과거가 있기 때문에 제외하고 다음으로 작은 숫자인 노드 3을 탐색한다.(순서3) 

 

노드 3과 연결된 2, 4 노드 중에서 역시나 노드2는 탐색했었기 때문에 노드4를 탐색하도록 한다.(순서4) 

 

연결된 노드를 모두 탐색했지만 노드1과 연결이 끊겨 있는 노드 5는 탐색을 하지 않고 끝나게 된다.

 

(코드 구현)

탐색할 때마다 순서가 부여되므로 노드 순위를 매기기 위해서는 따로 배열을 만들어서 배열의 인덱스와 원소 값을 가지고 순위와 노드번호를 탐색 시 저장하도록 한다.

 

오름차순 정렬

보통 일반적으로 dfs 는 노드를 탐색할 때 가장 작은 노드를 우선으로 방문하므로 오름차순 정렬을 선행해야한다.

문제에서도 "인접 정점은 오름차순으로 방문한다."라고 언급하기도 했다.

 

 

 

🌱 풀이.  

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

public class Main {
	static int cnt;
	static int[] checked;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        StringTokenizer strTo;

		strTo = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(strTo.nextToken());
		int m = Integer.parseInt(strTo.nextToken());
		int r = Integer.parseInt(strTo.nextToken());

		checked = new int[n + 1];

		// 그래프 초기화
		for (int i = 0; i <= n; i++) {
			graph.add(new ArrayList<Integer>());
		}
		// list에 값 저장
		for (int i = 0; i < m; i++) {
			strTo = new StringTokenizer(br.readLine(), " ");
			int u = Integer.parseInt(strTo.nextToken());
			int v = Integer.parseInt(strTo.nextToken());

			graph.get(u).add(v);
			graph.get(v).add(u);
		}
		for (int i = 1; i <= n; i++) {
			Collections.sort(graph.get(i));
		}

		cnt = 1;
		dfs(r);

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

	}

	private static void dfs(int node) {

		checked[node] = cnt;

		for (int i = 0; i < graph.get(node).size(); i++) {
			int newNode = graph.get(node).get(i);
			if (checked[newNode] == 0) {
				cnt++;
				dfs(newNode);
			}
		}

	}
}

 

 

 

---

중첩 ArrayList

연결된 노드들을 나열하기 위해 ArrayList 중첩을 사용한다.

ArrayList에 데이터를 저장하고 읽어오기 전에 두 번에 걸쳐 새 인스턴스를 생성하여 초기화 시키도록 한다. 

 

 

순위 저장

노드만큼의 크기로 노드 순위를 저장할 배열을 선언한다.

노드 번호가 배열의 인덱스로 갈 것이므로 배열의 크기는 1이 추가된다.

 

 

오름차순 정렬

각 노드와 연결된 노드들끼리 오름차순으로 되어 있으야 하므로,  ArrayList 안에 있는 또다른 ArrayList를 오름차순으로 정렬한다.

 

 

dfs 함수

탐색할 노드에 순위를 저장한 후 ArrayList 에 저장된 해당 노드와 연결된 노드들을 순서대로 탐색하는 함수이다.

노드 순위가 저장된 배열은 초기값이 0이기 때문에 순위가 매겨지게 되는 것은 다르게 보면 방문했다는 증거이기도 하다.

방문할 노드를 탐색할 때 조건문으로 순위 배열의 원소가 0일 때만들 골라 탐색하도록 한 것이다.

 

 

 

 

▶ Log

DFS 에 대한 이해 참고 사이트  : 나동빈 블로그

정렬하는 방법 참고 사이트 : https://hianna.tistory.com/569

 

드디어 그래프에 대해 알아보았다.

dfs는 stack, bfs는 queue와 연관된 알고리즘이라는 점이 코드를 구현하는데 중요한 출발선인 것 같다.

이 내용을 배제했다면 코드를 구현하는데 쉽지 않았을 것이다.