참고
문제해설
NOTE
•
입력 값 ⇒ n^2크기의 2차원 정수 배열(보드)
•
출력 값 ⇒ 광장(n^2)에 도달하기 위한 최소 이동수
•
한 번의 이동은 1~6(주사위) 범위내로 움직일 수 있다.
•
뱀이나 사다리가 존재하면, 해당 위치로 이동해야 한다.
문제 로직고민
NOTE
큐(int[]{x,y}) 생성
집합 방문여부 생성
큐.add(초기 시작위치와 움직인 횟수 0,0,0)
방문여부 .add(0,0)
while(큐가 빌때까지)
int[] 현재 좌표, 움직인 횟수
if(현재 좌표가 목적지임) return 움직인 횟수
for(i = 1~6)
// 이 부분 처리 고민 (이 문제의 난이도가 어려워지는 이유가 아닐까?)
int[] 움직인 좌표 = 현재좌표와 i를 통한 연산
int 값 = 좌표의 값
if(움직인 좌표에 뱀이나 사다리있음) 값 변경
if(움직인 좌표 방문안함)
큐.add(움직인 좌표, 움직인 횟수+1)
방문여부 .add(움직인 좌표)
Java
복사
•
BFS 방식으로 1~6 움직임에 대해 모두 넣어보며 탐색한다.
◦
BFS 방식으로 1~6범위를 방문하고, 방문처리를 한다.
◦
움직임에 따라 좌표값을 어떻게 변환시키는지가 중요하다.
•
1~6의 움직임으로 BFS에 넣어주는것은 간단하지만 좌표를 어떻게 알아내는가?
◦
ex) 6*6의 보드에서 15위치의 x와 y 좌표값을 알아내는 방법을 구해야한다.
◦
짝수 일때는 → 증가, 홀수 일때는 ← 증가
▪
y의 값 ⇒ 숫자 / n + 1
▪
x의 값 ⇒ y가 홀수( 숫자%n), 짝수 ( n-(숫자%n))
작성코드
NOTE
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
Queue<Integer> queue = new LinkedList();
Map<Integer, Integer> move = new HashMap();
queue.add(1);
move.put(1, 0);
while(!queue.isEmpty()){
int v = queue.poll();
if(v == n*n) return move.get(v);
for(int i=1; i<=6 && v+i <= n*n; i++){
int mv = v+i;
int[] mp = point(mv, n);
int my = mp[0];
int mx = mp[1];
if(!move.containsKey(mv)){
if(board[my][mx] != -1 && !move.containsKey(board[my][mx])) {
move.put(mv, move.get(v) + 1);
mv = board[my][mx];
move.put(mv, move.get(v) + 1);
}
else{
move.put(mv, move.get(v) + 1);
}
System.out.println(mv + " " + my + " " + mx);
queue.add(mv);
}
}
}
return -1;
}
private int[] point(int value, int n) {
int y = (n * n - value) / n;
int x;
if (y % 2 == 0) {
x = (n - 1) - (value - 1) % n;
} else {
x = (value - 1) % n;
}
return new int[]{y, x};
}
}
Java
복사
•
BFS논리는 크게 어렵지 않은데, Point의 좌표를 구하는것에서 좀 많이 애를 먹었다.
•
그런데 현재 로직은 테스트 케이스를 통과하지 못한다.
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
Queue<Integer> queue = new LinkedList();
Map<Integer, Integer> move = new HashMap();
queue.add(1);
move.put(1, 0);
while(!queue.isEmpty()){
int v = queue.poll();
if(v == n*n) return move.get(v);
for(int i=1; i<=6 && v+i <= n*n; i++){
int mv = v+i;
int[] mp = point(mv, n);
int my = mp[0];
int mx = mp[1];
int mvFinal = board[my][mx] == -1 ? mv : board[my][mx];
// value 값을 변경하는 부분수정
if(!move.containsKey(mvFinal)){
move.put(mvFinal, move.get(v) + 1);
queue.add(mvFinal);
}
}
}
return -1;
}
public int[] point(int s, int n) {
int quot = (s - 1) / n;
int rem = (s - 1) % n;
int row = n - 1 - quot;
int col = row % 2 != n % 2 ? rem : n - 1 - rem;
return new int[]{row, col};
}
}
Java
복사
그와중에 points 구하는방법 틀려서 그냥 검색했다… (BFS문제인지 Point 구하는 문제인지 원)
다른사람 풀이
NOTE
class Solution {
public int snakesAndLadders(int[][] board) {
int N = board.length;
int[] flatBoard = new int[N * N + 1];
int cellIdx = 1;
int colOffset = 1;
for (int row = N - 1; row > -1; row--) {
for (int col = colOffset == 1 ? 0 : N - 1; col < N && col > -1; col += colOffset) {
flatBoard[cellIdx++] = board[row][col];
}
colOffset *= -1;
}
int[] result = new int [N * N + 1];
Arrays.fill(result, -1);
result[1] = 0;
Queue<Integer> cells = new ArrayDeque<>();
cells.offer(1);
while (cells.size() > 0) {
int cell = cells.poll();
for (int nextCell = cell + 1; nextCell <= Math.min(cell + 6, N * N); nextCell++) {
int finalCell = flatBoard[nextCell] == -1 ? nextCell : flatBoard[nextCell];
if (result[finalCell] == -1) {
result[finalCell] = result[cell] + 1;
cells.offer(finalCell);
}
}
}
return result[N * N];
}
}
Java
복사
메모리를 적게 사용하는 코드
•
사실 메모리차이라고 해봐야 1MB정도이지만, Point를 구하는 식이 달라서 가져왔다.
class Solution {
static class Pair{
int num;
int level;
Pair(int num, int level){
this.num = num;
this.level = level;
}
}
public int snakesAndLadders(int[][] board) {
int n = board.length;
int [] values = new int[n*n ];
int currValue=0;
int count = 0;
for(int i = n-1 ;i >=0 ;i--){
if(count%2 == 0){
for(int j = 0;j< n ;j++){
values[currValue] = board[i][j];
currValue += 1;
}
}
else{
for(int j = n-1;j>=0;j--){
values[currValue] = board[i][j];
currValue += 1;
}
}
count += 1;
}
boolean[] visited = new boolean[n * n];
Queue<Integer> q = new LinkedList<>();
int start = values[0] > -1 ? values[0] - 1 : 0;
q.offer(start);
visited[start] = true;
int step = 0;
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
int cur = q.poll();
if (cur == n * n - 1) {
return step;
}
for (int next = cur + 1; next <= Math.min(cur + 6, n * n - 1); next++) {
int dest = values[next] > -1 ? values[next] - 1 : next;
if (!visited[dest]) {
visited[dest] = true;
q.offer(dest);
}
}
}
step++;
}
return -1;
}
}
Java
복사
시간이 더 빠른 코드
•
시간이 더 빠른 코드도 마찬가지로, n*n배열에 좌표값을 미리 구한다.