백준 - 1260번 - DFS와 BFS

1260번

시도하다 실패한 코드

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());

		Stack<Integer> stack = new Stack<>();
		boolean[] check = new boolean[N+1];
		boolean[][] arr = new boolean[N+1][N+1];
		for (int i = 0; i<M; i++) {
			StringTokenizer st2 = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st2.nextToken());
			int b = Integer.parseInt(st2.nextToken());
			arr[a][b] = true;
			arr[b][a] = true;
		}

		stack.push(V);
		System.out.print(V+" ");
		for (int j = 0; j<N; j++) {
			for (int i = 1; i<arr.length; i++) {
				if (arr[V][i] == true && check[i] == false) {
					stack.pop();
					System.out.print(i+" ");
					stack.push(i);

					check[V] = true;
					V = i;
					break;
				}
			}
		}

		Queue<Integer> queue = new LinkedList<>();
		queue.add(V);
//		System.out.print(V+" ");
		check[V] = true;
		for (int j = 0; j<N; j++) {
			for (int i = 1; i<N; i++) {
				if (arr[V][i] == true && check[i] == false) {
					queue.add(i);
					check[i] = true;
				}
			}
			if (!queue.isEmpty()) {
				System.out.print(queue.remove()+" ");
				V = queue.peek();
			}
		}

		while (!queue.isEmpty()) {
			System.out.print(queue.poll()+" ");

		}

	}
}

정답코드

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 Main {
	static StringBuilder sb = new StringBuilder();
	static boolean[] check;
	static boolean[][] arr;
	static int N, M, V;
	static Queue<Integer> queue = new LinkedList<>();

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		V = Integer.parseInt(st.nextToken());

		check = new boolean[N+1];
		arr = new boolean[N+1][N+1];

		for (int i = 0; i<M; i++) {
			StringTokenizer st2 = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st2.nextToken());
			int b = Integer.parseInt(st2.nextToken());
			arr[a][b] = true;
			arr[b][a] = true;
		}

		dfs(V);
		sb.append('\n');
		check = new boolean[N+1];
		bfs(V);

		System.out.println(sb);
	}

	static void dfs(int V) {
		check[V] = true;
		sb.append(V+ " ");

		for (int i = 1; i<N+1; i++) {
			if (arr[V][i] && !check[i]) {
				dfs(i);
			}
		}
	}

	static void bfs(int V) {

		queue.add(V);
		check[V] = true;

		while (!queue.isEmpty()) {
			V = queue.poll();
			sb.append(V+" ");

			for (int i = 1; i<N+1; i++) {
				if (arr[V][i] && !check[i]) {
					queue.add(i);
					check[i] = true;
				}
			}
		}
	}
}

풀이

---

주어진 수를 dfs와 bfs로 탐색하는 문제다.

노드와 간선과 시작점이 주어진다.

노드수+1만큼 노드경로를 확인했는지 check하는 배열하나, 노드간의 간선을 확인하는 2차원배열하나를 생성한다.

먼저 dfs다.
원래 정석은 스택을 이용해서 푸는것이지만 재귀를 사용해서 풀겠다.
메서드를 따로파서 시작점을 check해주고 sb에 추가한다. 그 후 2차원배열을 통해서 연결되있는 다음점과, 그 다음점이 check가 안됐는지 확인하고 조건에 충족하다면 처음과 같이 check해주고 sb에 추가한다.

bfs는 큐를 활용해서 풀겠다.
시작점을 큐에 넣고 check해준다.
while문으로 큐가 비어있을때까지 실행시켜주는데 먼저 시작점을 큐에서 빼주고 sb에 추가해준다.
그 2차원배열을 통해서 연결되어있는 다음점들과 check가 안됐는지 확인하고 조건에 충족하다면 모두 큐에 넣어주고 모두 check해준다.
반복문이 한번돌고 젤 앞단의 큐를 제거하고 제거한 값을 V에 대입한다. 그리고 sb에 추가한다. 반복문을 계속 돌린다.