[백준] 자바 1260 DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

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

출력

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

---

테스트 케이스

 

초록색 입력 / 검은색 출력

 

---

접근

정석대로 DBS는 재귀를 이욯아여서 풀고, BFS는 큐를 이용하여 문제를 해결하였습니다.

 

1. 3개의 숫자를 받는다

2. 처음 수는 정점 수, 두번째 수는 간선 수, 세 번째 수는 시작 정점

3. 간선수만큼 점끼리의 입력을 받는다 ex) 1 2면 점 1과 2 점가 연결된 것.

 

일단 2차원 배열을 이용해  입력받은 연결을 배열에 넣습니다.

1 2가 입력되었다면 1 배열에다 2 넣고, 2 배열에다가 1 넣는 식으로....

모든 배열을 넣어주었다면 배열마다 정렬을 한 번씩 해줍니다.

 

그러고 나서 visit을 체크하기 위해 점 개수만큼 visit배열을 생성해줍니다.

그리고 dfs함수에 시작 정점을 넣고 호출해주는데,

dfs함수 안의 주역할은 인자 정점 visit을 true로 바꿔주고 해당 점점을 출력함과 동시에 해당 점점과 연결된 점들(배열에 저장돼있는)을 하나씩 visit을 검사하여 이미 방문한 곳이라면(visit==true) 넘어가고(skip) 방문하지 않은 곳이라면 재귀 호출합니다.

이렇게 하여 모든 점을 (첫) 방문한 순서대로 출력하게 됩니다.

 

bfs도 마찬가지로 시작 정점을 가지고 호출하는데,

dfs와 같이 이미 방문한 곳이라면 skip 해주고 그렇지 않다면 q에 넣어주고 해당 q를 출력하며, 첫 인자 q배열에 해당하는 숫자들을 순서대로 검색하면서 없다면 q에 넣어주는 식으로 반복하게 됩니다.

이런 식으로 점들을 출력하게 됩니다.

---

코드

import java.awt.desktop.SystemEventListener;
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

	/*
 	 1260 problem
	*/

	static ArrayList<Integer>[] list;
	static boolean visit[];
			
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(st.nextToken());
		list = new ArrayList[N+1];
		
		for(int i=1;i<N+1;i++) {
			list[i] = new ArrayList<>();
		}
		for(int i=1; i<M+1; i++) {
			st = new StringTokenizer(br.readLine());
			int first = Integer.parseInt(st.nextToken());
			int second = Integer.parseInt(st.nextToken());
			
			list[first].add(second);
			list[second].add(first);
		}
		
		for(int i=1; i<N+1; i++) {
			Collections.sort(list[i]);
		}
		visit = new boolean[N+1];
		dfs(start);
		System.out.println();
		visit = new boolean[N+1];
		bfs(start);
		
		bw.flush();
		br.close();
		bw.close();
	}
	//dfs함수
	private static void dfs(int start) {
		if(visit[start]) {
			return;
		}
		else {
			visit[start] = true;
		System.out.print(start+" ");
		for(int i : list[start]) {
			if(!visit[i]) {
				dfs(i);
			}
		}
		}
		}
	//bfs함수
	private static void bfs(int start) {
		Queue<Integer> q = new LinkedList<>();
		if(visit[start]) {
			return;
		}
		else {
			visit[start] = true;
			q.add(start);
			while(!q.isEmpty()) {
				int num = q.poll();
				System.out.print(num+" ");
				for(int i : list[num]) {
					if(!visit[i]) {
						visit[i] = true;
						q.add(i);
					}
				}
			}
		}
	}
}

---

주의

x