백준 1520 '내리막 길'

Bonwoong Ku·2024년 10월 11일

BFS DFS ps 골드3 그래프 백준

알고리즘 문제풀이

목록 보기

109/110

하향식(Top-down) 풀이

아이디어

dfs(y, x)가 좌표 (0, 0)~(y, x)에 대한 경로의 경우의 수를 구하는 함수라 하자.
이때 dfs(y, x)는 4방향의 주변 칸 중 내리막으로 내려오는 칸 (y+dy[d], x+dx[d])에 대한 dfs 값의 합이다.
계산이 중복될 수 있는 부분은 memoization해두자.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer tk = null;

    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    static int M, N;
    static int[][] map;

    static int[][] memo;    // memo[y][x] = (0,0)~(y,x)까지 가기 위한 경우의 수

    public static void main(String[] args) throws Exception {
        tk = new StringTokenizer(rd.readLine());
        M = Integer.parseInt(tk.nextToken());
        N = Integer.parseInt(tk.nextToken());

        map = new int[M][N];
        memo = new int[M][N];

        for (int y=0; y<M; y++) {
            tk = new StringTokenizer(rd.readLine());
            for (int x=0; x<N; x++) {
                map[y][x] = Integer.parseInt(tk.nextToken());
                memo[y][x] = -1;
            }
        }

        memo[0][0] = 1;
        System.out.println(dfs(M-1, N-1));
    }

    static int dfs(int y, int x) {
        if (memo[y][x] != -1) return memo[y][x];
        int sum = 0;
        for (int d=0; d<4; d++) {
            int ny = y + dy[d];
            int nx = x + dx[d];
            if (ny < 0 || ny >= M || nx < 0 || nx >= N) continue;
            if (map[ny][nx] <= map[y][x]) continue;
            sum += dfs(ny, nx);
        }
        return memo[y][x] = sum;
    }
}

메모리 및 시간

메모리: 37440 KB
시간: 352 ms

상향식(Bottom-up) 풀이

아이디어

(0, 0)를 통해 내리막이 되는 칸들을 BFS로 탐색한다.
이때, 갈림길이 합쳐지는 교차점이 있다면, 교차점을 지나기 전에 각 갈림길 위의 점들을 모두 지나야하므로 순서를 지정해주기 위해 PriorityQueue을 이용하자.
갈림길이 합쳐질 때 경우의 수를 합치기 위해 모든 점에서의 값을 누적해 저쟝해야 한다. 여기서의 memo는 그것이라 하자.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer tk = null;

    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    static int M, N;
    static int[][] map;

    static int[][] memo;    // memo[y][x] = (0,0)~(y,x)까지 가기 위한 경우의 수
    static boolean[][][] enqueued;  // enqueued[y][x][d]: (y, x)에 d 방향으로 들어온 적이 있음

    static PriorityQueue<Coord> pq = new PriorityQueue<>();

    public static void main(String[] args) throws Exception {
        tk = new StringTokenizer(rd.readLine());
        M = Integer.parseInt(tk.nextToken());
        N = Integer.parseInt(tk.nextToken());

        map = new int[M][N];
        enqueued = new boolean[M][N][4];
        memo = new int[M][N];

        for (int y=0; y<M; y++) {
            tk = new StringTokenizer(rd.readLine());
            for (int x=0; x<N; x++) {
                map[y][x] = Integer.parseInt(tk.nextToken());
            }
        }

        memo[0][0] = 1;
        pq.offer(new Coord(0, 0));

        while (!pq.isEmpty()) {
            Coord coord = pq.poll();
            int y = coord.y;
            int x = coord.x;

            for (int d=0; d<4; d++) {
                int ny = y + dy[d];
                int nx = x + dx[d];
                if (ny < 0 || ny >= M || nx < 0 || nx >= N) continue;
                if (enqueued[y][x][d]) continue;
                if (map[y][x] <= map[ny][nx]) continue;

                memo[ny][nx] += memo[y][x];
                enqueued[y][x][d] = true;
                pq.offer(new Coord(ny, nx));
            }
        }

        System.out.println(memo[M-1][N-1]);
    }

    static class Coord implements Comparable<Coord> {
        int y, x;
        Coord(int y, int x) {
            this.y = y;
            this.x = x;
        }

        @Override
        public int compareTo(Coord o) {
            return -Integer.compare(map[y][x], map[o.y][o.x]);
        }
    }
}