[Java] 백준 1520 내리막 길 952hi의 접근방법

 

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

1520번: 내리막 길

---

1. 접근방법

보자마자 그저그런 최단거리 BFS 문제라고 판단하고 바로 큐에 넣어서 최단거리를 구해줬다.

예제 입출력 또한 잘나오지만 시간초과가 맞왜틀 발생한다.

 

단순하게 50*50*4 = 100,000 이라고 생각했지만 약 4의50약 2^100 => 엄청나게 큰수가 나와서

터지는 게 당연했다. 이 문제는 스스로 풀었다기 보다는 여러 정보를 조합해 스스로 풀어봤다.

 

메모이제이션과 DFS를 활용해 문제를 풀었다. BFS로 가능할지는 해보지않아서 모르겠다..

 

각 칸 별로 방문체크와 값이 다르면 바로 리턴을 해서 경우의 수를 줄이는 방식이다.

 

아래그림을 보면

시작 위치인 0,0에서 4방탐색 중 남쪽 방향을 통해 n,m향해 dfs로 진행했을때 가능한 경로라고 보면 마지막 n,m 도달하게 되면 지금까지 왔던 경로에 1을 리턴해준다.

 

두 번째 방향인 우측으로 탐색했을때 초록경로로 진행중 주황색을 경로를 침범 즉 이미 다녀간 부분을 접근하려한다면

이미 끝까지 갈수 있다는 말과 같다. 그러므로 바로 1의 경우의 값을 리턴해준다.

 

결론적으로 0,0 으로 오면 주황과 초록 경로의 합인 2가 되는 것이다.

 

느낀점 및 실수

메모이제이션을 map[i][j][1] += dfs(nx,ny) 와 같이 모든 경로를 탐색한 후 돌아오면서 갱신되게 하면 굉장히 효율적이다

시간이 많이 절약되는 것 같고 이해하기 전에는 왜? 라는 생각을 많이했는데 그림그리면서 이해하니 쉽게 이해할 수 있었다. 

 

또한 방문배열을 아에 사용하지않고 값이 0이 아니라면이 같은 맥락이라고 생각했는데 전혀 그렇게 되지않았다.

이부분 또한 기억을 해두어야 겠다고 생각했다.

 

코드

import java.io.*;
public class boj1520 {
	static class Reader {
		int bfs = 1 << 16;
		byte[] buffer = new byte[bfs];
		int bufferPos = 0, bufferState = 0;
		DataInputStream dis = new DataInputStream(System.in);

		byte read() {
			if (bufferPos == bufferState) {
				try {
					bufferState = dis.read(buffer, bufferPos = 0, bfs);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (bufferState == -1)
					buffer[0] = -1;
			}
			return buffer[bufferPos++];
		}

		int nextInt() {
			int rtn = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				rtn = rtn * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -rtn;
			return rtn;
		}
	}
	static int row,col,map[][][];
	static boolean visited[][];
	public static void main(String[] args) {
		Reader in = new Reader();
		row = in.nextInt();
		col = in.nextInt();
		// 0 -> 오르내리막 정보
		// 1 -> 메모이제이션 길 왕복횟수
		map = new int[row][col][2];
		visited = new boolean[row][col];
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				map[i][j][0] = in.nextInt();
			}
		}
		dfs(0,0);
		System.out.println(map[0][0][1]);
	}
	static int[][] dxdy = { { 0, 0, 1, -1 }, { 1, -1, 0, 0 } };
	private static int dfs(int i, int j) {
		if(i==row-1 && j==col-1) {
			return 1;
		}
		if(map[i][j][1]!=0) return map[i][j][1];
		
		if(!visited[i][j]) {
			visited[i][j] = true;
			int nx,ny;
			for(int k=0;k<4;k++) {
				nx = i + dxdy[0][k];
				ny = j + dxdy[1][k];
				if(0<=nx && 0<=ny && nx<row && ny<col && map[nx][ny][0] < map[i][j][0]) {
					map[i][j][1] += dfs(nx,ny);
				}
			}
		}
		return map[i][j][1];
	}
}