백준 - [ 1520: 내리막 길 ]

문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

예제 입력 1

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

예제 출력 1

실패한 코드

처음엔 아래와 같은 코드로 풀었다. 이동할 수 있는 횟수를 담을 cnt 배열을 생성하고, 받아온 값이 담긴 board 배열을 처음부터 돌면서 해당 칸의 높이 값이 상하좌우의 높이 값보다 낮다면 cnt배열에 값을 추가시켜주도록 했다.

실패한 코드-1

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

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

        int[][] cnt = new int[M + 2][N + 2];
        cnt[1][1] = 1;
        // 여기서 문제 발생
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                if (board[i][j] < board[i - 1][j]) cnt[i][j] += cnt[i - 1][j];
                if (board[i][j] < board[i][j - 1]) cnt[i][j] += cnt[i][j - 1];
                if (board[i][j] < board[i + 1][j]) cnt[i][j] += cnt[i + 1][j];
                if (board[i][j] < board[i][j + 1]) cnt[i][j] += cnt[i][j + 1];
            }

        }

        System.out.println(Arrays.deepToString(cnt));


        bw.write(cnt[M][N] + "");
        bw.flush();
        bw.close();
        br.close();
    }

}

그런데 예제 답이 다르게 나와서 보니, cnt 배열 값을 계산하는 과정에 문제가 있었다. 우선 행 내에서 -> 방향으로 계산하고 그 다음 행으로 넘어가는 이런 방식이라 계산할 당시에 우측 칸과 아래 칸의 값은 무조건 0이었다.

따라서 아래와 같이 우선 전과 같이 해당 칸에서 좌측 칸/위 칸 값을 비교해서 cnt값을 계산한 후, 좌측 칸/위 칸 값과 비교해서 해당 칸에서 계산한 값을 다시 더해주도록 수정했다.

실패한 코드-2

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

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

        int[][] cnt = new int[M + 2][N + 2]; // 이동 횟수 담을 배열
        cnt[1][1] = 1;
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                if (board[i][j] < board[i - 1][j]) cnt[i][j] += cnt[i - 1][j]; // 위 칸
                if (board[i][j] < board[i][j - 1]) cnt[i][j] += cnt[i][j - 1]; // 좌측 칸

                if (board[i-1][j] < board[i][j]) cnt[i-1][j] += cnt[i][j]; // 위에 칸 계산해줌
                if (board[i][j-1] < board[i][j]) cnt[i][j-1] += cnt[i][j]; // 좌측 칸 계산해줌
            }

        }

        System.out.println(Arrays.deepToString(cnt));


        bw.write(cnt[M][N] + "");
        bw.flush();
        bw.close();
        br.close();
    }

}

그런데 또 틀렸다고 나왔다. 그래서 질문게시판을 뒤져 반례를 확인해보니

3 3
9 4 3
8 5 2
7 6 1

아.. 내가 잘못 생각하고 있었음을 알 수 있었다. 위에 칸과 좌측 칸을 계산해주는 과정에서 거기서 그칠게 아니라 연결된 높이가 작은 값들에 모두 값을 더해줘야 했다. 따라서 BFS를 이용한 코드를 추가해주었다.

실패한 코드-3

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

class Point {
    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static int M, N;
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int[][] board, cnt;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

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

        cnt = new int[M + 2][N + 2]; // 이동 횟수 담을 배열
        cnt[1][1] = 1;
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                if (board[i][j] < board[i - 1][j]) cnt[i][j] += cnt[i - 1][j]; // 위 칸
                if (board[i][j] < board[i][j - 1]) cnt[i][j] += cnt[i][j - 1]; // 좌측 칸

                if (board[i - 1][j] < board[i][j]) BFS(i - 1, j, cnt[i][j]); // 위에 칸 계산해줌
                if (board[i][j - 1] < board[i][j]) BFS(i, j - 1, cnt[i][j]); // 좌측 칸 계산해줌
//                System.out.println(Arrays.deepToString(cnt));
            }
//            System.out.println();

        }


        bw.write(cnt[M][N] + "");
        bw.flush();
        bw.close();
        br.close();
    }

    public static void BFS(int x, int y, int val) {
//        System.out.println(x + " " + y + " " + val);
        Queue<Point> que = new LinkedList<>();
        que.offer(new Point(x, y));
        cnt[x][y] += val;

        while (!que.isEmpty()) {
            Point tmp = que.poll();
            for (int i = 0; i < dx.length; i++) {
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if (nx >= 1 && nx <= x && ny >= 1 && ny <= N && board[nx][ny] < board[tmp.x][tmp.y]) {
                    cnt[nx][ny] += val;
                    que.offer(new Point(nx, ny));
                }
            }

        }

    }
}

그런데 26% 즈음에서 메모리 초과가 뜬다. 방문 체크 없이 조건 만족할 때 마다 BFS를 돌리니 그런 듯 하다.

BFS를 이용해 첫번째 칸부터 높이가 작은 칸들을 큐에 추가하고 방문횟수를 체크하도록 코드를 수정했지만 역시 메모리 초과가 떴다. 마찬가지로 방문 체크없이 조건 만족하는 칸을 모두 큐에 추가해서 그런가보다.

실패한 코드-4

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

class Point {
    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int[][] board, cnt;
    static int M, N;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        board = new int[M][N];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        cnt = new int[M][N]; // 이동 횟수 담을 배열
        cnt[0][0] = 1;
        BFS(new Point(0, 0));

        bw.write(cnt[M - 1][N - 1] + "");
        bw.flush();
        bw.close();
        br.close();
    }

    public static void BFS(Point p) {
        Queue<Point> que = new LinkedList<>();
        que.offer(p);

        while (!que.isEmpty()) {
            Point tmp = que.poll();
            for (int i = 0; i < dx.length; i++) {
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if (nx >= 0 && nx < M && ny >= 0 && ny < N && board[nx][ny] < board[tmp.x][tmp.y]) {
                    cnt[nx][ny]++;
                    que.offer(new Point(nx, ny));
                }
            }
        }
    }

}

1. BFS+Priority Queue

구글링해보니 BFS+PQ를 이용한 풀이를 찾을 수 있었다.

나는 방문체크 없이 큐에 모든 경우를 넣어서 방문 횟수를 하나하나 카운트하는 방식이라 시간 복잡도가 4의n승 만큼 늘어날 수 있었다면, PQ를 이용하면 높이 순으로 내림차순 한 후, 방문 횟수를 더해주고 방문하지 않은 칸만 큐에 추가해주도록해서 O(MN)만에 끝낼 수 있었다.

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

class Point implements Comparable<Point> {
    int x, y, height;

    public Point(int x, int y, int height) {
        this.x = x;
        this.y = y;
        this.height = height;
    }

    public int compareTo(Point p) {
        return p.height - this.height;
    }
}

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int[][] board, cnt;
    static int M, N;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        board = new int[M][N];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        cnt = new int[M][N]; // 이동 횟수 담을 배열
        cnt[0][0] = 1;
        BFS(new Point(0, 0, board[0][0]));

        bw.write(cnt[M - 1][N - 1] + "");
        bw.flush();
        bw.close();
        br.close();
    }

    public static void BFS(Point p) {
        PriorityQueue<Point> pQ = new PriorityQueue<>();
        pQ.offer(p);

        while (!pQ.isEmpty()) {
            Point tmp = pQ.poll();
            for (int i = 0; i < dx.length; i++) {
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if (nx >= 0 && nx < M && ny >= 0 && ny < N && board[nx][ny] < tmp.height) {
                    if (cnt[nx][ny] == 0) {
                        pQ.offer(new Point(nx, ny, board[nx][ny]));
                    }
                    cnt[nx][ny] += cnt[tmp.x][tmp.y];
                }
            }
        }
    }

}

메모리	시간
36912 KB	444 ms

2. DFS

BFS 풀이를 구글링하는데 대부분 DFS를 이용해 문제를 푸셔서 생각해보니 해당 문제는 최소 방문 횟수가 아니라 총 방문 횟수를 구하는 문제이므로 BFS보다 DFS가 좀 더 목적에 맞는 풀이이지 싶다.

처음에 DFS로만 모든 경우의 수를 탐색해서 방문 횟수를 구했을 때는 시간 초과가 떴다. 방문 체크가 없으니 O(4^25000)가 될 수 있었겠다. 따라서 아래와 같이 top-down 방식으로 메모이제이션을 이용했다.

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

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int[][] board, cnt;
    static int M, N;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        board = new int[M][N];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        cnt = new int[M][N]; // 이동 횟수 담을 배열
        for (int i = 0; i < M; i++) {
            Arrays.fill(cnt[i], -1); // 방문 체크 위해 -1로 초기화
        }

        DFS(M - 1, N - 1);

        bw.write(cnt[M - 1][N - 1] + "");
        bw.flush();
        bw.close();
        br.close();
    }

    public static int DFS(int x, int y) {
        if (cnt[x][y] != -1) return cnt[x][y];
        if (x == 0 && y == 0) return 1;

        cnt[x][y] = 0; // 방문 체크
        for (int i = 0; i < dx.length; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < M && ny >= 0 && ny < N && board[nx][ny] > board[x][y]) {
                cnt[x][y] += DFS(nx, ny);
            }
        }
        return cnt[x][y];

    }


}

메모리	시간
35472 KB	432 ms

참조

https://sohee-dev.tistory.com/77

[백준/boj] 1520: 내리막 길 / BFS / Priority Queue / DP

문제 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지

sohee-dev.tistory.com

https://loosie.tistory.com/m/371

[BOJ] 백준 1520번 내리막 길 (Java)

#1520 내리막 길 난이도 : 골드 4 유형 : DP / DFS 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은

loosie.tistory.com

'6. 자료구조 & 알고리즘 > 6-2. 백준' 카테고리의 다른 글

백준 - [ 1049번: 기타줄 ] (0)	2023.07.29
백준 - [ 11657: 타임머신 ] (0)	2023.07.29
백준 - [ 1024번: 수열의 합 ] (0)	2023.07.22
백준 - [ 1018번: 체스판 다시 칠하기 ] (0)	2023.07.22
백준 - [ 1012번: 유기농 배추 ] (0)	2023.07.22

문제

입력

출력