[백준] 단계별로 풀어보기(단계:25, 그래프와 순회,JAVA)24479번, 알고리즘 수업 - 깊이 우선 탐색 1

문제 링크

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

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

DFS(깊이 우선 탐색)은 아래 그림처럼 어떤 조건을 가지고 목표노드에 도달하기까지 자식노드를 통해 이동하며 목표노드까지 도달하는 것을 말합니다.

자식 노드에 도착하면 그 자식노드에서 조건에 만족하는 자식노드로 다시 이동하여 목표 노드로 이동합니다.

 

출처 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

DFS

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

 

 

이 문제에 핵심은

1. 정점과 간선의 정보를 이용해서 출발 정점에서 각 정점을 방문하는 순번을 결과로 출력한다.

2. 간선은 무방향입니다.

3. 방문하지 않는 정점의 순번은 0으로 표현한다.

4. 정점 오름차순으로 깊이 우선 탐색을 진행합니다.

 

그래프에 대한 내용을 정의하기 위해 ArrayList<ArrayList<Integer>>의 형태로 리스트를 만들어주었습니다.

위와 같이 정의하여 데이터를 저장하면 각 정점이 어떤 정점으로 이동하는지 간단하게 저장할 수 있습니다.

예를 들어 

1 -> 4

1 -> 3

2 -> 5

3 -> 4

ArrayList<ArrayList<Integer>>의 저장되는 모습은 리스트 안에 리스트가 포함되는 형식으로 저장됩니다.

정점
1	3	4
2	5
3	1	4
4	1	4
5	2

 

그래프의 값을 리스트에 저장하였다면 출발 정점에서 DFS탐색을 시작하여 방문하는 순번을 구하였습니다.

 

예제 입력1에서 첫 번째 테스트케이스의 그래프를 표로 확인하며 보여드리겠습니다.

아래는 예제로 주어진 그래프입니다.

그래프의 내용이 저장된 ArrayList<ArrayList<>>의 해당하는 표

정점
1	2	4
2	1	3	4
3	2	4
4	1	2	3
5

1. 시작 정점 1부터 깊이 탐색을 진행합니다.

 

그래프 내용인 ArrayList<ArrayList<Integer>>을 이용하여 인접한 정점을 탐색합니다.

 

그래프에서 정점1과 인접한 정점은 2, 4이지만 오름차순으로 1 -> 2로 탐색합니다.

 

2. 깊이 우선으로 정점 2에서 인접한 정점 탐색합니다.

 

그래프에서 정점2과 인접한 정점은 1, 3, 4이지만

 

1은 탐색을 방문을 완료한 상태입니다.

 

2 -> 3으로 탐색합니다.

3. 깊이 우선으로 정점 3에서 인접한 정점 탐색합니다.

 

그래프에서 정점3과 인접한 정점은 2, 4이지만

 

2는 탐색을 방문을 완료한 상태입니다.

 

3 -> 4으로 탐색합니다.

 

4. 깊이 우선으로 정점 4에서 인접한 정점 탐색합니다.

 

그래프에서 정점4과 인접한 정점은 1, 2, 3이지만

 

1, 2, 3은 탐색을 방문을 완료한 상태입니다.

현재 깊이에서는 더 이상 탐색을 종료하고 이전 깊이로 이동합니다.

 

5. 이전 깊이 정점 2에서 인접한 정점 탐색합니다.

그래프에서 정점2과 인접한 정점은 1, 3, 4이지만

 

1, 3, 4는 탐색을 방문을 완료한 상태입니다.

현재 깊이에서는 더 이상 탐색을 종료하고 이전 깊이로 이동합니다.

 

6. 이전 깊이 정점 1에서 인접한 정점 탐색합니다.

 

그래프에서 정점1과 인접한 정점은 2, 4이지만

 

2, 4는 탐색을 방문을 완료한 상태입니다.

더 이상 이전 깊이가 존재하지 않기 때문에 깊이 우선 탐색은 종료합니다.

 

각 과정에서 정점을 방문할 때 순서를 배열에 저장한 뒤 결과로 출력하였습니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 그래프에 대한 정보를 ArrayList<ArrayList<Integer>>에 저장합니다.

2. DFS(깊이 우선 탐색)을 이용하여 시작정점 R에서 탐색을 시작합니다.

3. 각 정점을 방문할 때 방문한 순번을 배열에 저장합니다.

4. DFS탐색이 종료한 뒤 순번을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 그래프에 대한 정보를 저장하였습니다.
• 그래프에 내용 저장할 ArrayList<ArrayList<Integer>> graph를 만들었습니다.
• DFS로 그래프의 시작정점부터 탐색을 진행하는 bfs 함수를 만들었습니다.
• BufferedWriter에 DFS탐색으로 얻은 방문 순번을 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• dfs은 visited[], graph와 재귀를 이용하여 방문 여부 확인과 순번을 배열에 저장 및 탐색하였습니다.

결과 코드

import java.util.*;
import java.io.*;
public class Main {
	static int N,M,R,count=1;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();	//그래프 저장 리스트
	static boolean[] visited;		//정점 방문 확인 배열
	static int[] result;		//순번 저장 배열
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
        	//리스트 및 배열 초기화
		visited = new boolean[N+1];
		result = new int[N+1];
		for(int i=0;i<=N;i++) {
			graph.add(new ArrayList<Integer>());
		}
		for(int i=0;i<M;i++) {
			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);
		}
		dfs(R);		//DFS 탐색 시작
		for(int i=1;i<=N;i++)		//순번 저장된 배열 BufferedWriter 저장
			bw.write(result[i] + "\n");
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//DFS으로 시작정점에서 탐색을 시작하는 함수
	static void dfs(int cur) {
		visited[cur] = true;		//방문 확인
		result[cur] = count++;		//방문 순번 저장
		Collections.sort(graph.get(cur));	//인접 정점 오름차순 정렬
        	//인접 정점 탐색
		for(Integer value : graph.get(cur)) {
			if(!visited[value]) {	//방문하지 않았을 때
				dfs(value);
			}
		}
		return;
	}
}