[DFS/BFS] 백준 1260번 DFS와 BFS(Java)

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

1260번: DFS와 BFS

📚 문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더이상 방문할 수 있는 점이 없는 경우 종료한다.

 

첫째 줄에 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력	예제 출력
4 5 1 1 2 1 3 1 4 2 4 3 4	1 2 4 3 1 2 3 4

 

📝 문제 해결

가장 기본적인 DFS/BFS 문제
너무 오랜만에(?) 풀어서 가물가물했다.. 겨ㄹ혼은 선택,, 복습은 필수,,

 

📌 DFS (깊이 우선 탐색) / BFS (너비 우선 탐색) 란?

DFS (재귀함수)

1. node를 방문하면, 방문을 기록하고 node의 값을 출력한다.
2. 방문한 node에 연결된 다른 node배열을 받는다.
3. node배열중에서 방문하지 않은 배열이 있다면, node를 방문하고 (1)부터 반복한다.

BFS (Queue)

1. node를 방문하면, 방문을 기록하고 방문한 node를 Queue에 add하고 출력한다.
2. node에 연결된 다른, 방문하지 않은 node들을 Queue에 add한다.
3. Queue가 isEmpty가 참일때까지 반복한다.

(출처 : https://velog.io/@youswim96/백준-1260번-자바JAVA)

 

 

💻 코드

import java.io.*;
import java.util.*;

public class Main {
	static int N,M,V;
	static int[][] dfs, bfs;
	static boolean[] dVisited, bVisited;
	static StringBuilder sb;
	public static void main(String[] args) throws 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());
		
		dfs = new int[N+1][N+1];
		bfs = new int[N+1][N+1];
		dVisited = new boolean[N+1];
		bVisited = new boolean[N+1];
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int m = Integer.parseInt(st.nextToken());
			int n = Integer.parseInt(st.nextToken());
			dfs[m][n] = dfs[n][m] = 1;
			bfs[m][n] = bfs[n][m] = 1;
		}
		
		sb = new StringBuilder();
		dfs(V);
		sb.append("\n");
		bfs(V);
		System.out.println(sb);
	}
	
	public static void dfs(int node) {
		dVisited[node] = true;
		sb.append(node + " ");
		for(int i = 1; i<= N; i++){
			if(dfs[node][i] == 1 && !dVisited[i]){
				dfs(i);
			}
		}
	}
	
	public static void bfs(int node) {
		Queue<Integer> que = new LinkedList<>();
		bVisited[node] = true;
		que.offer(node);
		
		while(!que.isEmpty()) {
			int temp = que.poll();
			sb.append(temp + " ");
			for(int i=1; i<=N; i++) {
				if(bfs[temp][i] == 1 && !bVisited[i]) {
					bVisited[i] = true;
					que.offer(i);
				}
			}
		}
	}
}