백준 온라인 저지 - 1260번: DFS와 BFS

🔍 문제

---

 

말그래도 입력값으로 주어진 그래프를 dfs와 bfs로 탐색한 결과를 출력하면 된다.

1260번: DFS와 BFS

 

✏️ 풀이 - Java

---

 

Codility에서는 함수 인자로 필요한 값들이 주어기 때문에 함수 안에서 필요한 코드를 작성해주고 문제에서 원하는 값을 return 해주면 된다. 하지만 온라인 저지 사이트에서는 표준 입력값이 주어지고, 입력을 받아서 return이 아닌 다시 출력을 해주어야 한다.
따라서 문제에 필요한 값을 입력받는 것부터 익숙해지는데 좀 걸렸다. 익숙한 언어가 JS라 문제를 풀 수 있는 언어에 nodeJS도 있는 것을 봤는데 이것저것 찾아보니 JS로 풀다보면 변수만 선언해도 메모리초과로 못푸는 문제들도 있는 것 같고, 지원하는 모든 언어가 해당 문제를 풀 수 있다는 의미는 아닌 것 같았다.
이 사이트에서 문제 풀때는 C++이나 자바가 가장 많이 사용되는 것 같았는데, 나는 C++은 모르니 Java로 풀게되었다. 아래 풀이는 마이구미님의 풀이 방법을 보고 참고해서 풀어 보았다. 먼저, 인접리스트를 활용해 풀어보고 다음으로는 인접행렬로도 풀어보았다.

 

마이구미님의 블로그 링크로 가기 👉 마이구미의 Hello World

BFS와 DFS의 개념을 알고 싶다면 👉 BFS(너비우선탐색)와 DFS(깊이우선탐색)

 

인접 리스트로 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
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 br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); //정점의 개수 
        int m = Integer.parseInt(st.nextToken()); //간선의 개수 
        int v = Integer.parseInt(st.nextToken()); //탐색 시작 정점 


        //방문 체크 배열
        boolean[] c = new boolean[n+1];

        //인접리스트
        ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n + 1];

        for(int i = 0; i <= n; i++) {
            a[i] = new ArrayList<Integer>();
        }

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            a[v1].add(v2);
            a[v2].add(v1);
        }

        //정점이 여러 개인 경우 정점 번호가 작은 것부터 먼저 방문해야 하기 때문에 정렬을 해준다.
        for(int i = 0; i < n+1; i++) {
            Collections.sort(a[i]);
        }

        boolean flag = false;

        //DFS - stack 방식으로 할 경우 dfs(a, c, v, flag);

        dfs(a, c, v);

        System.out.println();
        Arrays.fill(c, false);
        bfs(a, c, v);
    }

    // DFS - 재귀 + 인접리스트
    private static void dfs(ArrayList<Integer>[] a, boolean[] c, int v) {
        //이미 방문한 정점일 경우 return
        if(c[v]) return;

        //방문했다고 true로 표시 한 후 print 해줌 
        c[v] = true;
        System.out.print(v + " ");

        for(int vv : a[v]) {
            if(!c[vv]) { //방문하지 않은 경우에만
                dfs(a, c, vv);
            }
        }
    }

    // DFS - Stack + 인접리스트 
    private static void dfs(ArrayList<Integer>[] a, boolean[] c, int v, boolean flag) {
        Stack<Integer> stack = new Stack<>();
        int n = a.length-1;

        stack.push(v);
        c[v] = true;
        System.out.print(v + " ");

        while(!stack.isEmpty()) {
            int vv = stack.peek();

            flag = false;

            for(int i : a[vv]) {
                if(!c[i]) {
                    stack.push(i);

                    System.out.print(i + " ");
                    c[i] = true;
                    flag = true;
                    break;
                }
            }

            if(!flag) {
                stack.pop();
            }
        }
    }

    // BFS + 인접리스트
    private static void bfs(ArrayList<Integer>[] a, boolean[] c, int v) {
        Queue<Integer> q = new LinkedList<>();

        q.add(v);
        c[v] = true;

        while(!q.isEmpty()) {
            v = q.poll();
            System.out.print(v + " ");

            for(int vv: a[v]) { //해당 v와 연결된 정점들 
                if(!c[vv]) { //방문하지 않은 경우에만 
                    q.add(vv); //큐에 넣어
                    c[vv] = true; //방문함 표시 
                }
            }
        }

    }

}

 

인접 행렬로 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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 br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());

    //방문 체크 배열 
    boolean[] c = new boolean[n+1];

    //인접행렬 만들기 
    int[][] a = new int[n+1][n+1];


        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            a[v1][v2] = 1;
            a[v2][v1] = 1;

        }

    boolean flag = false;
    //DFS - stack 방식으로 할 경우 dfs(a, c, v, flag);

    dfs(a, c, v);
    System.out.println();
    Arrays.fill(c, false);
    bfs(a, c, v);

    }

    //DFS - 재귀 + 인접행렬
    private static void dfs(int[][] a, boolean[] c, int v) {
        int n = a.length-1;

        c[v] = true;
        System.out.print(v + " ");

        for(int i = 1; i <=n; i++) {
            if(a[v][i] == 1 && !c[i]) {
                dfs(a, c, i);
            }
        }
    }

    //DFS - Stack + 인접행렬 
    private static void dfs(int[][] a, boolean[] c, int v, boolean flag) {
        Stack<Integer> stack = new Stack<>();

        int n = a.length - 1;

        stack.push(v);
        c[v] = true;

        System.out.print(v + " ");

        while(!stack.isEmpty()) {
            int vv = stack.peek();

            flag = false;

            for (int i =1; i <= n; i++) {
                if(a[vv][i] == 1 && !c[i]) {
                    stack.push(i);
                    System.out.print(i + " ");

                    c[i] = true;
                    flag = true;
                    break;
                }
            }

            if(!flag) { //막다른 길일경우 pop해주면서 가장 가까운 경로로 다시 돌아가야함.
                        //(=모두 방문했고 더 이상 연결된 정점이 없을 경우 flag = false)
                stack.pop();
            }
        }
    }

    //BFS - 인접행렬 
    private static void bfs(int[][] a, boolean[]c, int v) {
        Queue<Integer> q = new LinkedList<>();

        int n = a.length-1;
        q.add(v);
        c[v] = true;

        while(!q.isEmpty()) {
            v = q.poll();
            System.out.print(v + " ");

            for(int i = 1; i <= n; i++) {
                if(a[v][i] == 1 && !c[i]) {
                    q.add(i);
                    c[i] = true;
                }
            }
        }
    } 
}

풀긴 풀었지만 아직 나도 머릿속에 바로 그려지는 건 아니라서 직접 행렬과 리스트를 그려서 dfs 와 bfs 탐색을 했을 때 어떤 순서로 탐색이 진행되는 것인지 그려보면서 이해하니 많은 도움이 됐다. 몇개의 문제를 더 풀면서 익숙해질 필요가 있을 것 같다.