자바 - 백준 1520 / 내리막 길

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

골드3

구현 방법

잘못된 접근

BFS를 통해서 상,하,좌,우 를 탐색하여

1. 인덱스 범위에 있고,

2. 갈 곳의 높이가 현재 높이 보다 작은 경우

갈 수 있는 경로를 더해주는 방식으로 구현했습니다.

또한 한번도 도착하지 않은 경우에는 큐에 넣어 탐색을 진행할 수 있도록 했습니다.

 

하지만 이렇게 하는 경우, 나중에 추가된 경로의 개수가 반영되지 않는 문제가 발생했습니다.

이는 한 번 방문한 노드의 경우 다시 탐색하는 과정이 없기 때문에 추가된 경로의 개수가 업데이트되지 않기 때문이였습니다.

 

해결 방법

나중에 경로를 추가하는 상황을 만들지 않도록 하면 됩니다.

현재 문제에서는 높은 건물에서 낮은 건물로 간다는 방향성이 있습니다.

이를 통해 다음 경로를 정하기 전에 모든 경로를 이미 계산하면 됩니다.

따라서 우선 순위 큐를 통해 높은 건물 순으로 먼저 꺼내서 계산을 하도록 구현하면 위의 문제점을 해결할 수 있습니다.

 

코드

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

/**
* 백준 1520
* 내리막 길
* 골드3
* https://www.acmicpc.net/problem/1520
*/
public class Boj1520 {

    private static class Node implements Comparable<Node> {
        int x, y, h;

        Node(int x, int y, int h) {
            this.x = x;
            this.y = y;
            this.h = h;
        }

        @Override
        public int compareTo(Node n) {
            return Integer.compare(n.h, h);
        }
    }


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

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

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

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        map = new int[M][N];

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

        System.out.println(bfs());
    }

    public static int bfs() {
        int[][] dp = new int[M][N];
        dp[0][0] = 1;

        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(0, 0, map[0][0]));

        while(!q.isEmpty()) {
            Node cur = q.poll();

            if(cur.x == M - 1 && cur.y == N - 1)
                continue;

            if(map[cur.x][cur.y] <= map[M -1][N - 1])
                continue;

            for(int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if(nx < 0 || nx >= M || ny < 0 || ny >= N)
                    continue;

                if(map[cur.x][cur.y] <= map[nx][ny])
                    continue;

                if(dp[nx][ny] == 0)
                    q.add(new Node(nx, ny, map[nx][ny]));
                dp[nx][ny] += dp[cur.x][cur.y];
            }
        }

        return dp[M - 1][N - 1];
    }
}