알고리즘/백준

[백준] 1260번 - DFS와 BFS

땀두 2022. 3. 22. 07:50

 

DFS, BFS의 탐색을 둘 다 사용해서 해결하는 문제이다. 다른 문제들로 연습을 많이 해보아서 어렵지 않게 해결할 수 있었다. BFS와 DFS의 탐색이 어떻게 이루어지는지, 어떻게 구현하는지 원리를 안다면 쉽게 풀 수 있다.

 

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 p1260 {
	public static int a;
	public static int b;
	public static int[][] ary;
	public static boolean[] visitedBfs;
	public static boolean[] visitedDfs;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		int s = Integer.parseInt(st.nextToken());
		ary = new int[a + 1][a + 1];
		visitedBfs = new boolean[a + 1];
		visitedDfs = new boolean[a + 1];

		for (int i = 0; i < b; i++) {
			st = new StringTokenizer(br.readLine());
			int j = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());

			ary[j][k] = 1;
			ary[k][j] = 1;
		}

		dfs(s);
		System.out.println();
		bfs(s);
	}

	public static void bfs(int s) {
		Queue<Integer> q = new LinkedList<>();
		q.add(s);
		visitedBfs[s] = true;
		System.out.print(s + " ");
		while (!q.isEmpty()) {
			int n = q.poll();

			for (int i = 1; i <= a; i++) {
				if (ary[n][i] == 1 && visitedBfs[i] == false) {
					q.add(i);
					visitedBfs[i] = true;
					System.out.print(i + " ");
				}
			}
		}
	}

	public static void dfs(int s) {
		if (visitedDfs[s] == true) {
			return;
		}

		visitedDfs[s] = true;
		System.out.print(s + " ");

		for (int i = 1; i <= a; i++) {
			if (ary[s][i] == 1 && visitedDfs[i] == false) {
				dfs(i);
			}
		}
	}
}