[백준] 1520번 : 내리막 길 - 자바(JAVA

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

1520번: 내리막 길

 

문제 이해

지도 사이의 이동은 상하좌우 이웃한 곳끼리만 가능하다.

세준이의 출발점은 가장 왼쪽 위칸이며 목적지는 가장 오른쪽 아래입니다.

가능함 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표지점으로 가고자 한다.

 

 

문제 풀이 전 설계

가장 간단하게 드는 생각은 DFS/BFS로 경로를 세주는 것입니다.

N과 M의 크기는 500입니다.

항상 자신보다 적은길로 가야 하기 때문에 가지치기가 잘 될 것 같기는 한데 계속 4방향을 탐색해야 하므로 시간 초과가 조금 걱정됩니다.

 

완전 탐색으로 풀 수 없다면.. 경로를 기록해두어야 할 것 같습니다.

경로를 기록해두는 DP를 사용해야 할 것 같은데 어떻게 사용해야 할까요?

2차원 DP [y][x]를 사용하고 각 지점마다 경우의 수를 기록하면 될 것 같습니다.

 

문제 풀이하면서

DFS로 코드를 자던중 메모리 초과가 발생했습니다.

500 x 500에서 메모리 초과보다는 stack을 계속 쌓으므로 거기서 메모리 초과가 발생한 것 같습니다.

 

DFS와 DP를 접목시켜야 합니다.

인접 4방향을 탐색하면서 재귀 형태로 최종 목적지까지 타고 들어갈 경우에는 중간중간 겹치는 경우의 수가 발생하기 때문에 시간 복잡도가 좋지 않습니다.

 

오르막 -> 내리막으로 이동하기 때문에 한번 이동한 경우에는 더 이상 오르막으로 이동할 필요가 없기 때문에 추가 경로가 생길 시 방법을 +1씩 누적시키면서 해결합니다.

 

 

다음과 같은 경우를 예시로 살펴보겠습니다.

 

처음 걱정했던 것은 1번 경로는 막혀있는데 1번 경로를 이동하면서 방문 체크를 해버리게 되면 안 되지 않나..?라고 생각했습니다.

 

하지만 목적지에 도착한 경우에만 방문 체크를 해주게 되면 이는 해결됩니다!

 

1,2,3,4번 경로만 존재한다고 생각하고 DP 배열을 이동시켜 보겠습니다.

또한 탐색 우선순위는 오른쪽, 아래, 왼쪽, 위라고 가정하겠습니다.

 

여기서 -1은 방문되지 않음, 0은 방문됨, 경로가 존재하면 +1씩 증가됩니다.

초기 DP 배열

-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1

 

탐색 우선순위가 오른쪽, 아래, 왼쪽, 위 이기 때문에 1번 경로가 가장 먼저 DFS로 탐색됩니다.

0	0	0	0	0
-1	-1	-1	-1	0
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1

 

1번 경로는 막히게 되었으므로 DFS가 pop()되면서  4번 경로를 탐색하러 갑니다. (오른쪽 다음에는 아래 우선순위!)

0	0	0	0	0
-1	-1	-1	0	0
-1	-1	-1	0	-1
-1	-1	-1	0	0

 

이번에는 목적지에 도착했습니다. 경로가 존재하기 때문에 +1씩 해서 방문 체크를 진행해줍니다.

1	1	1	1	0
-1	-1	-1	1	0
-1	-1	-1	1	-1
-1	-1	-1	1	1

 

이제 3번, 2번 경로를 탐색하러 갑니다. ( 우선순위에 따라 3번 경로를 먼저 탐색합니다.)

1	1(경로겹침 발생)	1	1	0
0	0	-1	1	0
0	0	-1	1	-1
-1	-1	-1	1	1

탐색하다가 경로에 -1이 아닌 값을 만났습니다.

이는 "해당 경로로 이미 탐색을 해봤다"를 의미하며 1 이상이라면 경로가 존재하는 것이고, 0이라면 경로가 존재하지 않는 것입니다.

 

경로 3번으로 가던 중 이미 경로가 존재하기 때문에 더 이상 탐색하지 않고 +1씩 해서 방문 체크를 진행해줍니다.

2	1(경로겹침 발생)	1	1	0
1	1	-1	1	0
1	1	-1	1	-1
-1	-1	-1	1	1

 

이제 경로 2번을 탐색하러 갑니다.

2	1	1	1	0
1	1	-1	1	0
1	1	-1	1	-1
0	0	0	1(경로겹침 발생)	1

탐색하다가 경로에 -1이 아닌 값을 만났습니다.

이는 "해당 경로로 이미 탐색을 해봤다"를 의미하며 1 이상이라면 경로가 존재하는 것이고, 0이라면 경로가 존재하지 않는 것입니다.

 

경로 2번으로 가던 중 이미 경로가 존재하기 때문에 더 이상 탐색하지 않고 +1씩 해서 방문 체크를 진행해줍니다.

만약 해당 경로가 존재하지 않는다면! 막힐 때까지 탐색하고 +1씩 하지 않고 그냥 기존 값을 그대로 가지고 있습니다.

3	1	1	1	0
2	1	-1	1	0
2	1	-1	1	-1
1	1	1	1(경로겹침 발생)	1

 

이렇게 되면 DP [0][0]에는 갈 수 있는 경로가 저장되게 됩니다.

 

코드

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

public class Main_1520_내리막길 {

	static class Pos {
		int y;
		int x;

		public Pos(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

		@Override
		public String toString() {
			return "Pos [y=" + y + ", x=" + x + "]";
		}

	}

	static int M, N, result;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static int[][] board,DP;

	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()); // 가로

		board = new int[M][N];
		DP = new int[M][N];
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				DP[i][j] = -1; //DP배열 -1로 초기화
			}
		}

		DFS(new Pos(0, 0));
		System.out.println(DP[0][0]);
	}

	private static int DFS(Pos pos) {
		
		//도착지점에 도달하면 경우의 수 1을 return
		if (pos.x == N - 1 && pos.y == M - 1) {			
			return 1;
		}
		
		//해당 경로가 이미 방문되어 경로의 수가 계산된 적이 있는 경우
		if(DP[pos.y][pos.x] != -1) {
			return DP[pos.y][pos.x];			
		}
		
		//방문됨을 체크
		DP[pos.y][pos.x] = 0;
		
		for (int k = 0; k < 4; k++) {
			
			int tempY = pos.y + dy[k];
			int tempX = pos.x + dx[k];
			
			if (!isValid(tempY, tempX) || board[pos.y][pos.x] <= board[tempY][tempX]) {
				continue;
			}
			DP[pos.y][pos.x] += DFS(new Pos(tempY,tempX));
						
		}

		//나머지 경로에 대하여 계산된 경로의 수 return        
		return DP[pos.y][pos.x];
	}

	private static boolean isValid(int tempY, int tempX) {
		return tempY >= 0 && tempX >= 0 && tempY < M && tempX < N;
	}

}

 

 

출처

https://alwaysbemoon.tistory.com/187

[백준 1520, Java] 내리막 길