[Java] 백준 1520번 : 내리막 길*

1. 문제

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

1520번: 내리막 길

 

 

 

2. 풀이 과정

100x100까지는 단순한 DFS로 풀어도 빠르지만, 이 문제는 최대 map의 크기가 500x500이다. 따라서 간 곳은 또 갈 필요가 있을지 생각해봐야 한다.

 

여기서는 미래를 이미 알고 있는 건 다시 가지 않아도 되므로 이를 cnt[][]에 기록하였다.

자세한 동작 과정은 아래와 같다.

 

1. cnt[][]의 값을 -1로 초기화 (안 간 곳은 -1, 간 곳은 0이상으로 표시하기 위함)

2. dfs로 탐색 시작

     2-1. (방문 안 했던 곳만 옴)방문하면, 먼저 0으로 세팅한다.

     2-2. 네 방향을 보면서, 갈 수 있는 경로만큼 더해준다.

     2-3. 자신에서 목적지까지 갈 수 있는 경로의 수를 다 계산했으면, 이 값을 지나온 길에 업데이트해준다.

 

 

테스트 케이스를 만들어 실행 과정을 보면, 아래와 같다. 

[map]
50 45 37 32
35 50 20 25
30 30 17 28
27 22 15 10

 

cnt 배열 결과

 

3	2	2	1
1	-1	1	1
1	-1	1	-1
1	1	1	1

 

 

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

public class Main {
	static int N, M, map[][], cnt[][];
	
	public static int dfs(int x, int y) {
		int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
		
		if(x==N-1 && y==M-1) { return 1; }//목적지
		
		cnt[x][y] = 0;
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(0<=nx && nx<N && 0<=ny && ny<M && map[nx][ny] < map[x][y]) {//내리막길이면 가자
				if(cnt[nx][ny]!=-1) {//방문했다면
					cnt[x][y] += cnt[nx][ny];
				}
				else {//방문 안 했다면
					cnt[x][y]+=dfs(nx, ny);//왔던 길에 더하기
				}
			}
		}
		return cnt[x][y]; //네 방향 모두 둘러보고 업데이트 했다면
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		cnt = 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());
				cnt[i][j] = -1;//가는 길의 개수, -1은 아직 방문 전
			}
		}
		dfs(0, 0);
		System.out.println(cnt[0][0]);
	}
}