LeetCode 909 Snakes and Ladders 풀러가기

문제

이 문제는 이해하는데 한참이나 걸렸다. 영어로 되어 있기도 하고, 문제에 주어진 조건들이 꽤 복잡했다.

문제는 다음과 같다.

위의 그림 처럼 보드는 N*N으로 주어진다.

N*N 보드에서 가장 왼쪽, 가장 아래쪽이 1이 되고, 오른쪽방향으로 +1 된다. 가로 N줄이 채워지면 그 위칸부터, 다시 왼쪽으로 숫자를 채운다.

만약 3*3이라면 보드는 다음과 같이 된다.

7	8	9
6	5	4
1	2	3

이렇게 생긴 보드에서 문제의 목표는 1칸에서 시작해서, N*N칸에 도달하는 최소한의 이동횟수를 구하는 것이다.

도달 할 수 없다면 -1을 반환한다.

이동하는 규칙은 다음과 같다.

갈 수 있는 다음 칸은 주사위를 굴려서 가는 것인데, 주사위의 숫자는 1부터 6까지 있다.

그래서 갈 수 있는 칸의 범위는 ( 현재칸 + 1 ~ Math.min(현재칸 +6, N*N) ) 이다.

그런데, 이 보드는 사다리와 뱀을 가지고 있어서 주사위 숫자를 넘어 다른 칸으로 이동할 수 있는 것이다.

각 칸의 정보가 주어지는데, -1 이라면 사다리 또는 뱀이 없는 것이고,

-1이 아닌 숫자가 있다면 그 숫자의 칸으로 바로 이동할 수 있다.

사다리 또는 뱀이 있는 칸에 갔다면, 무조건 사다리 또는 뱀을 이용해서 다른 칸으로 이동해야 한다.

그 자리에 머물 수는 없다.

또한 추가로 사다리가 연속해서 있다면, 한번에 하나의 사다리만 이용할 수 있다.

예를 들어, 2칸에는 5로 가는 사다리가 있고, 5칸에는 9로 가는 사다리가 있다.

이럴때, 2칸에서 한번 5로 가는 사다리만 이용가능하다. 다음 번에 9로 이동하는 사다리를 이용할 수 있다.

만약 위에서 예로든, 3*3 보드에서 사다리의 정보가 2칸-> 5칸, 5칸->9칸이라고 주어졌을 때 , 정답은 2이다.

문제 분석

첫번째 시도

갈 수 있는 칸은 체크하면서 가는 BFS 방식을 생각했다.

이차원 배열 board를 바로 사용하려다가, 갈 수 있는 칸이 현재 노드의 상하좌우가 아니라,

현재 칸 + ( 1~6 ) 의 범위 이기에, 1차원 배열이 더 편할 것 같다고 생각했다.

그래서 현재 노드를 1차원 배열로 바꾸어 map이라는 배열에 저장하였다.

그 후, 1번 부터 Queue에 넣고, BFS를 하였다.

BFS 를 하며, 현재 노드가 board.length * board.length 에 도달하면 이를 return 하고,

모든 경우를 돌았는데도 도달하지 못하면 Queue가 비어있기 때문에, -1를 리턴하게 된다.

가장 주의했던 부분은 사다리가 연속해서 있을 때, 그 다음 값을 Queue에 넣어주는 부분이다.

이때, 다음 칸 (map[j])를 확인하고, -1이 아니면 사다리를 이용해야 하기에,

사다리를 이용해서 갈 수 있는 칸에 간 적이 없으면( if (!visited[map[j]]) ), 방문했음을 체크하고, queue에 넣었다.

코드

class Solution {
    public static int snakesAndLadders(int[][] board) {
		// Convert board to one-dimensional array(map)

		int[] map = new int[board.length * board.length + 1];
		boolean check = true;
		int index = 1;

		for (int i = board.length - 1; i >= 0; i--) {
			if (check) {
				for (int j = 0; j < board.length; j++) {
					map[index++] = board[i][j];
				}
			} else {
				for (int j = board.length - 1; j >= 0; j--) {
					map[index++] = board[i][j];
				}
			}
			check = !check;
		}
        
        // bfs

		boolean[] visited = new boolean[board.length * board.length + 1];
		Queue<Integer> queue = new LinkedList<>();

		queue.offer(map[1] == -1 ? 1 : map[1]);
		visited[1] = true;
		int count = 0;

		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				Integer curr = queue.poll();
                // 목적지에 도착했다면 count(depth) 리턴
				if (curr == board.length * board.length)
					return count;

				for (int j = curr + 1; j <= Math.min(curr + 6, board.length * board.length); j++) {
					if (map[j] == -1) {
						if (!visited[j]) {
							queue.add(j);
							visited[j] = true;
						}
					} else {
						if (!visited[map[j]]) {
							queue.add(map[j]);
							visited[j] = true;
							visited[map[j]] = true;
						}
					}
				}

			}
			count++;
		}

		return -1;
	}


    public boolean check(int destination, int size){
        return destination>=0 && destination<size;
    }
}

결과 : 성공

Runtime

Memory

문제를 꽤 오래 풀었는데, 시간도 괜찮았지만 무엇보다 메모리 효율이 좋아서 기분이 좋았다.

오래동안 고민한 보람이 있었다.