https://leetcode.com/problems/snakes-and-ladders
평가
결과 : 1회 실패 후 성공
풀이시간 : 57분
문제 조건을 잘못 파악해 한 번 틀렸다.
문제의 조건에서는 1부터 이동을 시작해 오른쪽으로 이동한다.
하지만 나는 n*n부터 이동을 시작해 오른쪽으로 이동하는 방식으로 문제를 풀어 한 번 틀렸다.(잘못읽음)
아이디어
해당 문제는 최단거리를 찾는 문제이기 때문에 bfs를 사용해 풀 수 있습니다.
인덱스에 실제 좌표값 매핑하기
문제의 복잡도를 낮추기 위해서는 Board에 적혀있는 숫자(인덱스라고 하겠습니다)와 실제 x,y좌표를 매핑시켜야 합니다.
쉽게 말해 36이라는 인덱스는 배열에서 (0,0)에 위치한다, 인덱스 1은 배열에서 (5,0)에 위치한다. 이런 식으로 매핑을 시켜주는 겁니다.
저는 가장 단순하게 for문을 돌려가며 각 인덱스의 좌표를 dp에 저장해주었습니다.
아이디어는 간단합니다.
1. 인덱스 1부터 출발해서 n*n까지 값을 채워줍니다.
2. 인덱스 1의 좌표는 (n, 0) 입니다.
3. y값을 1씩 추가합니다.(오른쪽으로 이동)
4. y값을 더이상 추가할 수 없으면 x값을 1 빼고, 이제부터 왼쪽으로 이동합니다.해당 아이디어를 구현한게 아래 코드입니다.
단순 구현이니 설명은 생략하겠습니다.
특정 인덱스 x의 좌표값을 찾고 싶다면 dp[x]를 확인하기만 하면 됩니다.
int n = board.length;
dp = new Node[n*n+1];
int i = n-1;
int j = 0;
int temp = 0;
boolean goRight = true;
for(int k=1; k<=n*n;k++) {
dp[k] = new Node(i, j);
temp++;
if (temp == n) {
i--;
temp = 0;
goRight = !goRight;
continue;
}
if (goRight) {
j++;
} else {
j--;
}
}
// System.out.println(Arrays.toString(dp));이동하기
현재 인덱스에서 1부터 6 사이의 값을 더한 인덱스로 이동이 가능합니다.
만약 이동한 위치에 사다리나 뱀이 있다면 뱀이나 사다리의 끝으로 이동하게 됩니다.
다시 말하면 이동한 인덱스를 좌표로 변환했을 때,
- board[i][j]가 -1이면 그 위치 그대로
- -1이 아니면(뱀이나 사다리가 있음) board[i][j]가 가리키는 인덱스로 이동합니다.
이렇게만 설명하면 너무 헷갈리니 다시 그림을 가져오겠습니다.
인덱스 1에서 출발해서 이동가능한 위치는 2,3,4,5,6,7 입니다.
위에서 만든 dp를 사용해 좌표를 가져올 수 있다고 말씀드렸죠?
2 -> (5,1) 3 -> (5,2) 4 -> (5,3) ...
인덱스 2는 (5,1)이라는 좌표값을 가졌습니다. board[5][1]는 -1이 아니라 15라는 값을 가졌네요.
이 말은 인덱스 2에 사다리나 뱀이 있다라는 의미로, 사다리가 가리키는 15로 이동하게 됩니다.
인덱스 1에서 출발해서 2를 거쳐 인덱스 15로 이동했네요.
인덱스 3은 (5,2)라는 좌표값을 가졌습니다. board를 보면 해당 값은 -1입니다.
그러니까 그냥 인덱스 1에서 출발해서 인덱스 3에 도착했다는 의미에요.
이러한 방식으로 현재 위치에서 갈 수 있는 위치들을 찾아줄 수 있습니다.
public int reindex(int idx) {
Node node = dp[idx];
if (board[node.x][node.y] == -1) {
return idx;
}
return board[node.x][node.y];
}
이제 목적지를 구할 수 있으니 BFS를 적용할 수 있겠죠?
자세한 건 코드를 통해 살펴보시길 바라겠습니다.
문제의 전제조건 중에는 사다리나 뱀이 중첩될 수 없다는 조건이 있었습니다.
그렇기 때문에 1에서 출발해서 인덱스 2에서 사다리를 타고 인덱스 15로 이동한 뒤 더이상 확인하지 않는거에요.
해당 조건이 없다면, 우리는 사다리나 뱀을 타고 이동한 후에도 반복을 통해 끝나는 위치를 찾아줘야 하겠죠?
정답 코드
class Solution {
static Node[] dp;
static int[][] board;
public int snakesAndLadders(int[][] board) {
this.board = board;
int n = board.length;
dp = new Node[n*n+1];
int i = n-1;
int j = 0;
int temp = 0;
boolean goRight = true;
for(int k=1; k<=n*n;k++) {
dp[k] = new Node(i, j);
temp++;
if (temp == n) {
i--;
temp = 0;
goRight = !goRight;
continue;
}
if (goRight) {
j++;
} else {
j--;
}
}
// System.out.println(Arrays.toString(dp));
int[] visited = new int[n*n+1];
Arrays.fill(visited, -1);
Queue<Integer> queue = new LinkedList<>();
visited[1] = 0;
queue.offer(reindex(1));
while(!queue.isEmpty()) {
int now = queue.poll();
for(int k=1; k<=6; k++) {
int next = reindex(now + k);
// System.out.println(now + "->" + next);
if (next > n * n) { // 판의 범위를 벗어나면
continue;
}
if(visited[next] != -1) { // 이미 방문한 적 있으면
continue;
}
// now + i가 어디로 이동할지 확인한다
visited[next] = visited[now] + 1;
queue.add(next);
if (next == n * n) {
return visited[n*n];
}
}
}
return visited[n*n];
}
public int reindex(int idx) {
Node node = dp[idx];
if (board[node.x][node.y] == -1) {
return idx;
}
return board[node.x][node.y];
}
static class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public String toString() {
return "(" + x+", " + y + ")";
}
}
}