[백준] 단계별로 풀어보기(단계:24, DFS와BFS,JAVA)1260번, DFS와 BFS

문제 링크

1260번: DFS와 BFS

---

주의사항

• 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

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

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

DFS

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

BFS

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

이 문제에 핵심은

1. 인접한 정점이 여러개 일 때 작은 정점을 먼저 방문한다.

2. DFS와 BFS를 구현한다.

 

정점은 1~N까지의 정점이 생성된다고 문제에 표현되기 때문에 정점의 연결을 표현하는 2차원 배열을 만들었습니다.

graph[N+1][N+1]

graph[i][j]의 값은 정점i와 정점j가 인접하고 있으면 1, 없으면 0을 저장하였습니다.

만약 정점 2와 정점 1이 인접하고 있다면

graph[2][1], graph[1][2]가 인접하다는 것을 표현하는 배열의 값이기 때문에 graph[2][1] = 1, graph[1][2] =1로 저장한다.

 

dfs를 구하는 것은 재귀를 사용하여 해결하였습니다.

조건은 낮은 정점를 먼저 탐색을 진행하도록 for문을 1부터 시작하여 가장 먼저 만나는 정점이 가장 낮은 정점입니다.

check배열을 통해서 해당 정점을 탐색했는지를 확인을 통해서 탐색하였습니다.

예제 입력1에서

시작정점이 1로 표현되었기 때문에

정점 1에서 인접한 정점는 2, 3, 4입니다.

가장 낮은 값을 먼저 탐색하기 때문에 정점 2를 탐색

정점 1 -> 정점 2

정점 2에서 인접한 정점는 1, 4입니다.

가장 낮은 값을 탐색해야 해서 1을 탐색하려고 하면 1은 시작정점로 벌써 탐색되었기 때문에 4를 탐색합니다.

정점 2 -> 정점 4

정점 4에서 인접한 정점는 1, 2, 3입니다.

가장 낮은 값을 탐색해야 하지만 1, 2는 탐색되었기 때문에 3을 탐색합니다.

정점 4 -> 정점 3

이제 다시 시작 정점 1로 가서 탐색을 해야 하지만 인접한 2, 3, 4가 모두 탐색되었기 때문에 탐색은 종료됩니다.

결과적으로 탐색한 순서는

정점 1 -> 정점 2 -> 정점 4 -> 정점 3 이 됩니다.

 

BFS는 Queue를 사용하여 문제를 해결하였습니다.

Queue에 기준이 될 수 있는 정점들을 저장하여 하나씩 꺼내서 인접한 정점들을 탐색하도록 하였습니다.

먼저 시작 정점를 Queue에 저장합니다.

Queue에 값을 꺼내서 그 값이 기준 정점로 인접한 정점를 찾아서 Queue에 저장합니다.

저장하는 이유는 인접한 정점를 모두 탐색한 뒤 그 인접한 정점를 기준으로 다시 탐색할 것이기 때문입니다.

위 과정을 반복하여 Queue에 값이 더 이상 꺼낼 수 없다면 모두 탐색한 것으로 판단할 수 있습니다.

예제 입력 1로 살펴보면

시작 정점를 Queue에 저장합니다.

1

Queue에서 값을 꺼내서 기준 정점로 잡고 인접한 정점를 찾습니다.

Queue에서 꺼낸 정점는 시작 정점였던 1입니다.

정점 1과 인접한 정점는 2, 3, 4으로 2, 3, 4를 Queue에 추가합니다.

2

3

4

다음 기준 정점를 통해 인접한 정점를 찾으려고 Queue에서 값을 빼냅니다.

Queue에서 꺼낸 정점는 2입니다.

정점 2와 인접한 정점는 1, 4이지만 모두 탐색을 진행했기 때문에 정점 2에서 인접한 정점 찾는 탐색을 종료합니다.

3

4

다음 기준 정점를 통해 인접한 정점를 찾으려고 Queue에서 값을 빼냅니다.

Queue에서 꺼낸 정점는 3입니다.

정점 3과 인접한 정점는 1, 4이지만 모두 탐색을 진행했기 때문에 정점 3에서 인접한 정점 찾는 탐색을 종료합니다

4

다음 기준 정점를 통해 인접한 정점를 찾으려고 Queue에서 값을 빼냅니다.

Queue에서 꺼낸 정점는 4입니다.

정점 4와 인접한 정점는 1, 2, 3이지만 모두 탐색을 진행했기 때문에 정점 4에서 인접한 정점 찾는 탐색을 종료합니다

Queue가 비어있으면 모두 탐색하였다고 판단하여 탐색을 종료합니다.

결과적으로 탐색한 순서는

정점 1(시작 정점) -> 정점 2 -> 정점 3 -> 정점 4가 됩니다.

 

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

1. graph[N+1][N+1] 과 check[N+1]로 정점의 개수만큼 초기화해줍니다.

2. 입력값을 받아서 graph에서 i와 j가 인접하면 1을 인접하지 않으면 0으로 저장하였습니다.

3. DFS(깊이 우선 탐색)를 재귀문을 사용하여 탐색 순서를 구하였습니다.

4. BFS(너비 우선 탐색)를 Queue와 반복문을 통해 탐색 순서를 구하였습니다.

5. DFS와 BFS 탐색 순서를 차례로 결과로 출력하였습니다.  

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 graph배열을 초기화해주었습니다.
• DFS와BFS탐색을 하는 dfs,bfs 함수를 만들었습니다.
• BufferedWriter에 DFS와 BFS의 탐색 순서를 차례대로 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• dfs은 check[], graph[][]와 재귀를 통해 탐색을 하였습니다.
• bfs는 check[], graph[][]와 Queue를 사용하여 탐색하였습니다.
• dfs/bfs는 낮은 정점을 먼저 탐색해야 하기 때문에 반복문을 1부터 시작하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int N,M,V;	//정점,간선, 시작 정점
	public static int[][] graph;	//i,j가 인접하는지 확인 배열
	public static boolean[] check;		//정점 탐색했는지 확인 배열
	public static StringBuilder sb = new StringBuilder();	//결과
    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());
    	V = Integer.parseInt(st.nextToken());
    	graph = new int[N+1][N+1];
    	check = new boolean[N+1];
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int x = Integer.parseInt(st.nextToken());
    		int y = Integer.parseInt(st.nextToken());
            /*
            정점 i와 정점 j가 인접하다는 것은
            [i][j] = 1, [j][i]= 1로 표현해야 합니다.
            */
    		graph[x][y]=1;
    		graph[y][x]=1;
    	}
    	dfs(V);		//dfs 탐색 함수 실행
    	sb.append("\n");
    	check = new boolean[N+1];		//탐색 확인 배열 초기화
    	bfs(V);		//bfs 탐색 함수 실행
    	bw.write(sb.toString());		//dfs와 bfs탐색 순서 BufferedWriter 저장
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();
    }
    //------DFS(깊이 우선 탐색) 진행 함수--------
    public static void dfs(int cur) {
    	sb.append(cur + " ");
    	check[cur] = true;		//해당 정점 탐색 완료
    	
    	for(int i=1;i<=N;i++) {		//조건이 낮은 정점 먼저 탐색이므로 1부터 반복시작
    		if(graph[cur][i]==1 && !check[i]) {
    			dfs(i);		//인접한 정점 중 탐색 가능하면 탐색
    		}
    	}
    	return;
    }
    //--------BFS(너비 우선 탐색) 진행 함수---------
    public static void bfs(int start) {
    	Queue<Integer> queue = new LinkedList<Integer>();
    	sb.append(start + " ");
    	check[start] = true;	//시작 정점 탐색 완료
    	queue.offer(start);		//시작 정점 기준 정점으로 사용하기 위해 Queue에 저장
    	while(!queue.isEmpty()) {
    		int location = queue.poll();	//기준 정점
    		for(int i=1;i<=N;i++) {	//조건이 낮은 정점 먼저 탐색으로 1부터 반복시작
    			if(graph[location][i]==1 && !check[i]) {
                		//기준 정점 기준으로 인접한 정점 탐색
    				check[i] = true;
    				queue.offer(i);
    				sb.append(i + " ");
    			}
    		}
    	}
    	return;
    }
}