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

문제

1520번: 내리막 길

풀이

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<Pos> {
		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 o.height - this.height;
		}
	}
	
	public static void main(String[] args) throws Exception {
		input();
		bfs();
		System.out.println(visited[N-1][M-1]);
	}

	private static void bfs() {
		PriorityQueue<Pos> 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<N; i++) {
			st= new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
	}
}

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

키포인트

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

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

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

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

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

 

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