[JAVA]BOJ[백준] - DFS와 BFS - 1260

- 문제 내용

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

1260번: DFS와 BFS

 

---

- 문제 접근 방법

단순히 DFS와 BFS를 구현해내면 되는 문제이다.  DFS, BFS 구현은 많은 사람들이 구현해 놓은 방식이 있는데 간선의 경우 2차원배열을 이용해서 풀었다. 그리고 DFS와 BFS 문제에 접근하기 전에 백트래킹 알고리즘 문제에 먼저 익숙해지고 시작하는 편이 수월할 것 같다.

---

- 풀이

• 입력값 및 배열 선언

public class BOJ_1260 {
	static int N; //정점의 개수
	static int M; //간선의 개수
	static int V; //시작 정점
	
	static int[][] arr; //연결된 간선(양방향)
	static boolean[] check; //방문 배열​

 

 

 

• Main

public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		V = Integer.parseInt(st.nextToken());
		
		check = new boolean[N+1]; //방문 배열
		arr = new int[N+1][N+1]; //간선 배열
		
		for(int i=0; i<M; i++) { //정점 v1, v2 사이에 간선이 존재하면 1을 넣어줌
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			arr[v1][v2] = 1;
			arr[v2][v1] = 1;
		}
		
		new BOJ_1260().dfs_solution(V);
		for(int i=0; i<check.length; i++) { //DFS 끝나고 check 배열 전부 false로 바꿈
			if(!check[i]) {continue;}
			check[i]=false;
		}
		System.out.println();
		new BOJ_1260().bfs_solution();
	}​

 

• DFS - 재귀사용

	public void dfs_solution(int depth) { // DFS 재귀방법
		check[depth]=true; // 시작 정점 방문처리
		System.out.print(depth+" "); // 방문한 정점 출력
		
		for(int i=1; i<=N; i++) { // 1~N까지 간선이 연결된 정점들 검사하면서 그중에 방문안한 정점만 재귀호출
			if(arr[depth][i]==1 && !check[i]) {
				dfs_solution(i);
			}
		}
	}

 

 

• BFS - 큐이용

	public void bfs_solution() { // BFS 큐이용
		Queue<Integer> queue = new LinkedList<Integer>();
		
		queue.add(V); // 큐에 시작정점 추가
		check[V] = true; // 시작정점 방문처리
		
		while(!queue.isEmpty()) { // 큐가 빌때까지 무한 반복
			int temp = queue.poll(); // 제일 앞에값 뽑음(방문한 정점)
			System.out.print(temp+" "); // 방문 정점 출력
			
			for(int i=1; i<=N; i++) { // 1~N까지 반복하며 DFS와 마찬가지로 간선과 해당 정점 방문 여부 확인.
				if(arr[temp][i]==1 && !check[i]) {
					queue.add(i); // temp값과 연결된 정점중 방문안한 정점 큐에 전부 추가.
					check[i]=true; // 방문 처리
				}//if
			}//for
		}//while
	}//bfs_solution

---

• 전체 코드

package org.boj.dfs.bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_1260 {
	static int N; //정점의 개수
	static int M; //간선의 개수
	static int V; //시작 정점
	
	static int[][] arr; //연결된 간선(양방향)
	static boolean[] check; //방문 배열
	
	public void dfs_solution(int depth) { // DFS 재귀방법
		check[depth]=true; // 시작 정점 방문처리
		System.out.print(depth+" "); // 방문한 정점 출력
		
		for(int i=1; i<=N; i++) { // 1~N까지 간선이 연결된 정점들 검사하면서 그중에 방문안한 정점만 재귀호출
			if(arr[depth][i]==1 && !check[i]) {
				dfs_solution(i);
			}
		}
	}
	
	public void bfs_solution() { // BFS 큐이용
		Queue<Integer> queue = new LinkedList<Integer>();
		
		queue.add(V); // 큐에 시작정점 추가
		check[V] = true; // 시작정점 방문처리
		
		while(!queue.isEmpty()) { // 큐가 빌때까지 무한 반복
			int temp = queue.poll(); // 제일 앞에값 뽑음(방문한 정점)
			System.out.print(temp+" "); // 방문 정점 출력
			
			for(int i=1; i<=N; i++) { // 1~N까지 반복하며 DFS와 마찬가지로 간선과 해당 정점 방문 여부 확인.
				if(arr[temp][i]==1 && !check[i]) {
					queue.add(i); // temp값과 연결된 정점중 방문안한 정점 큐에 전부 추가.
					check[i]=true; // 방문 처리
				}//if
			}//for
		}//while
	}//bfs_solution
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		V = Integer.parseInt(st.nextToken());
		
		check = new boolean[N+1]; //방문 배열
		arr = new int[N+1][N+1]; //간선 배열
		
		for(int i=0; i<M; i++) { //정점 v1, v2 사이에 간선이 존재하면 1을 넣어줌
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			arr[v1][v2] = 1;
			arr[v2][v1] = 1;
		}
		
		new BOJ_1260().dfs_solution(V);
		for(int i=0; i<check.length; i++) { //DFS 끝나고 check 배열 전부 false로 바꿈
			if(!check[i]) {continue;}
			check[i]=false;
		}
		System.out.println();
		new BOJ_1260().bfs_solution();
	}
}

 

DFS의 경우 함수의 매개변수에 depth가 정점이 되고 처음 depth는 V(시작정점)으로 전달한다. 그리고 재귀 호출하면서 정점을 하나하나 방문과 동시에 출력해 나간다. 마지막으로 방문할 정점이 더 이상 없을때 되돌아면서 함수가 종료된다.

 

BFS의 경우 큐를 이용하고 큐에 시작정점을 추가하고 큐에서 add했던 정점을 poll하면서 출력해준다. 그리고 poll한 정점 주변에 연결된 정점이 있는지 확인하고 있으면 poll한 정점과 연결된 모든 정점을 큐에 add한다. 그리고 다시 큐를 poll하면서 위의 과정을 큐가 빌때까지 반복하면된다!

 

Main에서 배열의 크기들을 N+1을 한이유는 0번째 인덱스는 쓰지않고 정점번호와 맞추기위해 1번 인덱스부터 사용했고 그래서 N+1을 했다.

---

- 마치며

최근 정처기 실기 시험때문에 알고리즘 문제를 많이 못보는데 얼른 정처기 시험 끝났으면 좋겠다ㅠ

그리고 문제를 풀기전에  DFS와 BFS 개념과 백트래킹에 대한 공부를 선행하는게 좋을것 같다!