[백준] 1520 내리막 길

1. 문제

www.acmicpc.net/problem/1520

1520번: 내리막 길

2. 접근방법

bfs나 dfs를 이용해 목적지까지 경로를 탐색하는 문제인데 문제는 목적지까지 갈 수 있는 경로의 갯수를 구해야 한다는 것이다.

 

일반적인 bfs나 dfs로는 모든 경로를 찾다가 터질게 분명하니 dp도 사용해줘야 한다.

 

위와 같이 20이 있는 위치로 가는 경로는 2가지이다.

그러므로 20에서 17로 가는경로도 2가지이고 

15로 가는 경로는 17에서 15로 2가지에 22에서 15로 가는 경로 1가지

총 3가지 15에서 10으로 가는 경로는 3가지가 된다.

 

 

그림으로 그리면 이런식인데

그냥 각 이동마다 한 위치에 가는 경로갯수를 저장하고 다음 경로로 넘어갈 때 가지고 있는 경로갯수만큼씩

넘어가면 된다.

 

그리고 height가 높은 순서대로 나와야 정상적인 경로 갯수를 찾을 수 있으니

Priority 큐를 사용해주자.

 

visit배열을 이용해 이미 도착한 구역이면 que에 넣지 않고 경로갯수에 +1 만 시켜줬다.

 

 

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class P1520내리막길 {

	static class point implements Comparable<point> {
		int x;
		int y;
		int height;

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

		@Override
		public int compareTo(point o) {
			return o.height - this.height;
		}
	}

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

		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int map[][] = new int[M][N];
		int count[][] = new int[M][N];
		boolean visit[][] = new boolean[M][N];
		int dr[] = { 1, -1, 0, 0 };
		int dc[] = { 0, 0, -1, 1 };
		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());
			}
		}
		count[0][0] = 1;
		PriorityQueue<point> que = new PriorityQueue<point>();
		que.add(new point(0, 0, map[0][0]));
		while (!que.isEmpty()) {
			point now = que.poll();

			for (int i = 0; i < 4; i++) {
				int row = now.x + dr[i];
				int col = now.y + dc[i];
				if (row < 0 || col < 0 || row >= M || col >= N)
					continue;
				if(map[now.x][now.y] <= map[row][col])
					continue;
				count[row][col] += count[now.x][now.y];
				if(visit[row][col])
					continue;
				
				visit[row][col] = true;
				que.offer(new point(row, col, map[row][col]));
			}
		}
		System.out.println(count[M-1][N-1]);

	}

}

4. 마치며

구현의 복잡도 보단 경로가 합쳐진다는 개념을 떠올리면 풀기 쉬운 문제였다.