백준 1260: DFS와 BFS (java)

BFS는 무난하게 풀었는데, DFS 때문에 이틀 걸렸다.

재귀로 풀면 쉽게 풀리는 문제라고 하지만 재귀를 잘 못해서 익숙한 스택으로 풀려했다.

 

근데 작은 숫자부터 방문하는 조건을 거는걸 아무리 해도 못하겠어서 오래걸렸고.. 지금도 못풀었다.

서치해서 코드를 봐도 이해가 안돼서 그냥 재귀로 풀었다.

---

알고리즘

DFS: 재귀

BFS: 큐

 

체감 난이도

★ ★ ★ ★ ☆

 

다시 풀 수 있는가?

YES

---

1. 양방향 간선

 

간선이 양방향이므로 이렇게 설정해줬는데 처음 써보는 문법이라 가져왔다.

 

arr[u][v] = arr[v][u] = 1;

 

2. DFS

 

방문 조건은 BFS와 같고, 재귀로 호출한다는 것만 다르다.

아무래도 깊이깊이 파고들어야하기 때문에 재귀로 호출하는 것 같다.

 

    public void DFS(int x) {
        isVisited[x] = true;
        System.out.print(x + " ");

        for (int i = 1; i <= N; i++) {
            if ((arr[x][i] == 1 || arr[i][x] == 1) && !isVisited[i]) {
                DFS(i);
            }
        }
    }

 

전체 코드 ▼

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

public class Main {
    int[][] arr;
    int N, M, V;
    boolean[] isVisited;

    public void DFS(int x) {
        isVisited[x] = true;
        System.out.print(x + " ");

        for (int i = 1; i <= N; i++) {
            if ((arr[x][i] == 1 || arr[i][x] == 1) && !isVisited[i]) {
                DFS(i);
            }
        }
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        // 인접 행렬 (간선 잇기)
        arr = new int[N+1][N+1];
        for (int i = 1; i <= M; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");

            int u = Integer.parseInt(st2.nextToken());
            int v = Integer.parseInt(st2.nextToken());

            arr[u][v] = arr[v][u] = 1; // 간선은 양방향
        }

        // DFS (재귀)
        isVisited = new boolean[N+1];
        DFS(V);
        System.out.println();

        // BFS (큐)
        Queue<Integer> q = new LinkedList<>();
        isVisited = new boolean[N+1];

        q.add(V);
        isVisited[V] = true;

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

            for (int i = 1; i <= N; i++) {
                if ((arr[k][i] == 1 || arr[i][k] == 1) && !isVisited[i]) {
                    q.add(i);
                    isVisited[i] = true;
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}