[Leetcode] 576. Out of Boundary Paths

문제 정의

m * n 의 격자판과 공이 주어졌을 때, 공의 첫번째 위치가 주어진다. 한번 움직일 때 공을 인접한 4곳의 위치로 이동할 수 있다고 할 때 maxMove 번 동안 공을 움직일 수 있게 허용된다.

m, n, startRow, startColumn, maxMove 가 주어질 때 격자판 밖으로 공을 나가게 할 수 있는 경로의 수를 구하고, 그 값은 매우 크기때문에 10의 9승 + 7 로 나눈 값을 반환하라. 

 

https://leetcode.com/problems/out-of-boundary-paths/

Out of Boundary Paths - LeetCode

 

풀이

처음에는 문제를 보고 어제 풀었던(695. Max Area of Island) 문제와 비슷하게 maxMove 만큼 bfs 탐색을 통해서 밖으로 공을 내보낼 수 있는 모든 경우를 탐색한다고 생각을 했다.

문제의 마지막 문장을 잘 읽어봤어야 했는데..  Since the answer can be very large, return it modulo 10의 9승 + 7 => 답이 매우 크기 때문에.. bfs 탐색으로 풀자마자 바로 시간초과가 발생했다.(73/94)

 

어떻게 해야 시간을 줄일 수 있을지 잘 감이 안와서 힌트를 열어봤는데 보자마자 DP 로 풀어야 하네? 싶었다.

Is traversing every path feasible? There are many possible paths for a small matrix. Try to optimize it.

모든 경로를 탐색할 수 있는가? 작은 매트리스여도 가능한 많은 경로가 있다. 최적화 해라!

 

DP 의 기본이니 점화식을 세워야겠다고 생각했고, 3차원 배열을 활용했다.

moves[n][i][j] = n번의 움직임을 통해 (i, j) 위치에 도달할 수 있는 경우의 수

= n-1번째의 (i, j) 좌표의 상하좌우에서 올 수 있기 때문에 인접한 4곳의 moves[n-1][a][b](a, b는 인접한 네 좌표의 좌표값) 의 합

예시를 보면 알 수 있듯이 다른 좌표를 찍고 다시 원래의 좌표로 돌아갈 수 있기 때문에 visited 등은 고려하지 않아도 된다.

위와 같이 점화식을 세워서 maxMove 까지 반복문을 통해 계산할 수 있다. 

계산을 하고 나면?! 2차원 배열들의 모든 가장자리 좌표는 한번 더 움직였을 때 밖으로 나갈 수 있는 경우의 수가 된다.

maxMove 이전에 이미 밖으로 나갈 수도 있으니 이 모든 경우의 수를 다 더해주면 된다!

그런데?????? 이렇게 값을 더해가면서도 10의 9승 + 7 로 값을 잘 나눠줘야한다. 경우의 수가 매우 크기 때문에 Int 범위를 벗어나는 경우가 생기고 오버플로우가 발생하면 구하고자 하는 값을 정상적으로 구할 수가 없다.

오버플로우를 간과해서 87번까지 통과했다가 수정했는데도 91번까지만 통과해서 만들어진 moves 를 디버깅해보니 이 배열 자체에도 오버플로우가 있었어서 중간중간 모듈러 계산을 다 넣어서 보완해줬다.

 

정답 코드

class Solution {
	public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
		int[] rows = {0, 1, 0, -1};
		int[] cols = {-1, 0, 1, 0};

		int shout = 0;

		int[][][] moves = new int[maxMove + 1][m][n]; // [move][m][n] -> (m,n) 자리에 movew 번의 움직임으로 올 수 있는 경우의 수
		moves[0][startRow][startColumn] = 1; // start 지점은 0번째 move 로 올 수 있음

		for (int move = 1; move < maxMove; move++) {
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					for (int a = 0; a < 4; a++) {
						if (i + rows[a] < 0 || i + rows[a] >= m || j + cols[a] < 0 || j + cols[a] >= n) {
							continue;
						}
						moves[move][i][j] =
							moves[move][i][j] % 1000000007 + moves[move - 1][i + rows[a]][j + cols[a]] % 1000000007;
					}
				}
			}
		}

		for (int move = 0; move < maxMove; move++) {
			for (int j = 0; j < m; j++) {
				shout = shout % 1000000007 + moves[move][j][0] % 1000000007;
				shout = shout % 1000000007 + moves[move][j][n - 1] % 1000000007;
			}
			for (int j = 0; j < n; j++) {
				shout = shout % 1000000007 + moves[move][0][j] % 1000000007;
				shout = shout % 1000000007 + moves[move][m - 1][j] % 1000000007;
			}
		}
		return shout % 1000000007;
	}
}

BFS 로 푼 코드 

class Solution {
	int[] rows = {0, 1, 0, -1};
	int[] cols = {-1, 0, 1, 0};

	public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
		Queue<Pair> queue = new LinkedList<>();
		int move = 1;
		int shout = 0;

		queue.add(new Pair(startRow, startColumn));
		while (!queue.isEmpty() && move <= maxMove) {
			int size = queue.size();

			for (int i = 0; i < size; i++) {
				Pair curr = queue.remove();

				for (int j = 0; j < 4; j++) {
					int nextX = curr.x + rows[j];
					int nextY = curr.y + cols[j];
					if (nextX < 0 || nextY < 0 || nextX >= m || nextY >= n) {
						shout++;
						continue;
					}
					queue.add(new Pair(nextX, nextY));
				}
			}
			move++;
		}

		return shout % (1000000000 + 7);
	}

	class Pair {
		int x;
		int y;

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

		public int getY() {
			return y;
		}

		public int getX() {
			return x;
		}
	}
}

생각보다 어렵넹 ^0^