백준 1260 - DFS와 BFS

예전에 c++로 풀었던 DFS BFS 문제를 자바로 다시 풀어봤다.

자바는 정말 익숙하지 않아 기본적인 입출력이나 배열 선언, 초기화부터 헤메느라 시간이 오래걸렸다.

그래프는 2차원 배열로 구현했다. 기회가 된다면 linked list로 구현하기도 해보고 싶다.

 

dfs는 재귀를 사용하여 무리없이 잘 풀었는데, bfs가 정말 오랜만이어서 큐를 사용해야 한다는 생각조차 못하고 있었다. 

dfs와 비슷한 방식으로 풀면 되겠지 하고 재귀를 가지고 끙끙거리다가 시간을 많이 썼다.

큐를 사용한다는 아이디어를 얻고 난 후에는 쉽게 풀었다.

 

import java.util.Scanner;
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    private static int n, m, v;
    private static int v1, v2;
    private static boolean [][] array;
    private static boolean [] visited;
    private static Queue<Integer> q = new LinkedList<>();

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        v = sc.nextInt();
        
        array = new boolean[n][n];
        visited = new boolean[n];

        for(int i = 0; i < m; i++){
            v1 = sc.nextInt();
            v2 = sc.nextInt();
            v1--;
            v2--;
            array[v1][v2] = true;
            array[v2][v1] = true;
            //이차원 인접 행렬을 사용하여 그래프를 나타내는 방식
        }

        dfs(v - 1);
        System.out.println();
        Arrays.fill(visited, false);
        bfs(v - 1);
    }

    private static void dfs(int idx){
        System.out.print(idx + 1 + " ");
        visited[idx] = true;
        for (int i = 0; i < n; i++){
            if (!visited[i] && array[idx][i]){
                dfs(i);
            }
        }
    }

    private static void bfs(int idx){
        if (!visited[idx]){
            System.out.print(idx + 1 + " ");
            visited[idx] = true;
        }
        for(int i = 0; i < n; i++){
            if (!visited[i] && array[idx][i]){
                System.out.print(i + 1 + " ");
                visited[i] = true;
                q.add(i);
            }
        }
        if (!q.isEmpty())
            bfs(q.poll());
    }
}​

 

해당 문제는 dfs와 bfs에 대한 기억을 되짚어보고자 맛보기로 풀어본 문제이다. 더 어려운 dfs bfs 문제에 도전해 볼 생각이다.