[백준] 22869번 - 징검다리 건너기 (small) [Java]

https://www.acmicpc.net/problem/22869

 

[백준] 22869번 - 징검다리 건너기 (small) [Java]

[백준] 22869번 - 징검다리 건너기 (small) [Java]

---

1.  아이디어

 

BFS, DFS, 다이나믹 프로그래밍 3가지 방법으로 해결했다.

---

2. 문제풀이

 

- BFS

해당 문제는 각 돌을 노드로 이동할 수 있는 돌에는 간선을 연결한다 했을 때 1번 노드에서 N번 노드를 방문할 수 있는지 BFS 알고리즘으로 파악할 수 있다. 이때 항상 오른쪽으로만 이동해야 하므로 유방향 간선 그래프가 됨에 주의해야 한다.

 

- DFS

1번 돌부터 시작하며 재귀는 현재 돌보다 숫자가 큰 돌들을 비교하며 방문할 수 있는 돌이면 방문하는 과정을 반복하고 방문 체크를 해줬다. 이후 N번 돌이 방문 체크가 되어있는지 확인하면 간단하게 구현할 수 있다.

 

- 다이나믹 프로그래밍

dp 배열은 갈 수 있는 돌을 체크한다. 1번 돌부터 반복문을 돌며 갈 수 있는 돌을 만나면 해당 돌부터 갈 수 있는 돌을 전부 찾아서 갈 수 있는 돌로 체크해줬다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main_BFS {
    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 K = Integer.parseInt(st.nextToken());

        int[] arr = new int[1 + N];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 1; i <= N - 1; i++) {
            for (int j = i + 1; j <= N; j++) {
                if ((j - i) * (1 + Math.abs(arr[i] - arr[j])) <= K) {
                    adj.get(i).add(j);
                }
            }
        }

        boolean flag = bfs(N, adj);

        if (flag) System.out.println("YES");
        else System.out.println("NO");
    }

    private static boolean bfs(int N, List<List<Integer>> adj) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(1);

        boolean[] visited = new boolean[1 + N];
        visited[1] = true;

        while (!q.isEmpty()) {
            int node = q.poll();

            if (node == N) return true;

            for (int next : adj.get(node)) {
                if (visited[next]) continue;

                q.offer(next);
                visited[next] = true;
            }
        }

        return false;
    }

}

import java.io.*;
import java.util.*;

public class Main_DFS {

    private static int N;
    private static int K;
    private static int[] arr;
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        arr = new int[1 + N];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        visited = new boolean[1 + N];

        dfs(1);

        if (visited[N]) System.out.println("YES");
        else System.out.println("NO");
    }

    private static void dfs(int cur) {
        if (visited[cur]) return;
        visited[cur] = true;

        for (int next = cur + 1; next <= N; next++) {
            if ((next - cur) * (1 + Math.abs(arr[cur] - arr[next])) <= K) {
                dfs(next);
            }
        }
    }

}

import java.io.*;
import java.util.*;

public class Main_DP {
    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 K = Integer.parseInt(st.nextToken());

        int[] arr = new int[1 + N];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        boolean[] dp = new boolean[1 + N];
        dp[1] = true;
        for (int i = 1; i <= N; i++) {
            if (!dp[i]) continue;

            for (int j = i + 1; j <= N; j++) {
                if ((j - i) * (1 + Math.abs(arr[i] - arr[j])) <= K) dp[j] = true;
            }
        }

        if (dp[N]) System.out.println("YES");
        else System.out.println("NO");
    }
}

---

4. 후기

 

- BFS

- DFS

- 다이나믹 프로그래밍