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

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

IT's easy, if you try

s5he2 2021. 4. 6. 22:13

풀이

import java.util.*; import java.io.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int N, M, total = 0; static int[][] map, visited; static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; private static class Pos implements Comparable { int x; int y; int height; public Pos(int x, int y, int height) { super(); this.x = x; this.y = y; this.height = height; } @Override public int compareTo(Pos o) { return this.height - o.height; } } public static void main(String[] args) throws Exception { input(); bfs(); System.out.println(visited[N-1][M-1]); } private static void bfs() { PriorityQueue pq = new PriorityQueue(); pq.add(new Pos(0,0,map[0][0])); visited[0][0] = 1; int nx, ny; while(!pq.isEmpty()) { Pos now = pq.poll(); for(int i=0; i<4; i++) { nx = now.x + dx[i]; ny = now.y + dy[i]; if(nx <0 || nx >= N || ny < 0 || ny >= M) continue; if(map[nx][ny] < map[now.x][now.y]) { if(visited[nx][ny] == 0) pq.add(new Pos(nx, ny, map[nx][ny])); visited[nx][ny] += visited[now.x][now.y]; } } } } private static void input() throws Exception { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); map = new int[N][M]; visited = new int[N][M]; for(int i=0; i

이 문제는 BFS 만 사용하면 메모리 초과가 난다.

키포인트

visited 배열: 현재 좌표까지 올 수 있는 경로의 수를 저장한다.

1. 높은 높이부터 poll 되도록 Pos 클래스에서 Comparable 를 implements 해야한다.

@Override public int compareTo(Pos o) { // 내림차순 return o.height - this.height; }

작은 높이부터 poll 되면, N-1, M-1 좌표까지 다다른 다음에 높이가 더 높은 좌표가 poll 되기 때문에 의미가 없어진다.

2. 현재보다 낮은 높이를 만났는데, visited가 0이 아닌 경우 (이미 전에 들림) 현재까지 오기까지의 경로의 수를 더해주기만하고 Priority Queue에는 더하지 않는다.

아직까지는 이해만 된 정도인데 나중엔 문제를 보자마자 떠올릴 수 있길 !

from http://sohee-dev.tistory.com/77 by ccl(A) rewrite - 2021-04-06 22:27:08