[Leetcode Top Interview 150] 909. Snakes and Ladders

난이도 : medium

문제링크

• n*n 의 2차원 정수 배열이 주어짐
• 배열의 각 원소는 역 좌우교대서법 스타일로 라벨이 되어진다
  • 맨 왼쪽 아래부터 읽혀짐
  • 줄이 바뀔때마다 글씨를 쓰는 방향이 반대가 됨
    • 글자의 모양도 반대가 됨
• 한번의 턴마다 [curr+1 ~ min(curr+6, n^2)] 의 범위로 움질일 수 있음
• 셀의 값은 -1 혹은 1~n^2
  • -1 : 일반 칸. 특정 범위로 이동하기
  • -1이 아님 : 해당 셀로 이동 (snake or labber)
• n^2 칸에 도착하면 게임이 종료됨
• 가장 적게 n^2에 도착하는 턴의 횟수를 리턴하라
  • 이동이 불가능하다면 -1을 리턴하라

 

1. 접근법

• 접근법 자체를 떠올리지 못했다
• 너무 어. 렵. 다. (ㅠㅠ)

 

6. 회고

• 감이 전혀 안잡혀 강의를 들었다

class Pair {
    int square;
    int moves;

    public Pair(int square, int moves) {
        this.square = square;
        this.moves = moves;
    }
}

class PositionOnBoard {
    int r;
    int c;

    public PositionOnBoard(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public int snakesAndLadders(int[][] board) {
    int n = board.length;

    Collections.reverse(Arrays.asList(board));

    Set<Integer> visited = new HashSet<>();
    Queue<Pair> queue = new LinkedList<>();
    queue.add(new Pair(1, 0));

    while (!queue.isEmpty()) {
        Pair pair = queue.poll();
        int square = pair.square;
        int moves = pair.moves;

        for (int i = 1; i <= 6; i++) {
            int nextSquare = square+i;
            PositionOnBoard newPosition = positionOnBoard(nextSquare, n);
            if (board[newPosition.r][newPosition.c] != -1) {
                nextSquare = board[newPosition.r][newPosition.c];
            }

            if (nextSquare == n*n) {
                return moves+1;
            }

            if (!visited.contains(nextSquare)) {
                visited.add(nextSquare);
                queue.add(new Pair(nextSquare, moves+1));
            }
        }
    }

    return -1;
}

private PositionOnBoard positionOnBoard(int square, int n) {
    int r = (square-1)/n;
    int c = (square-1)%n;
    if (r%2 != 0) {
        c = n-1-c;
    }
    return new PositionOnBoard(r, c);
}

(출처 : NeetCode github)

• 이 문제는 BFS 문제이다
  • 완전탐색을 해야 한다 (그리디 알고리즘 X)
  • 너비탐색을 하면서, 목적지까지 도착하는데 걸린 턴수를 리턴한다
• 맨아래 첫번째 열에서 n*n 칸까지 가는데 계산이 어려우므로
  • 주어진 배열을 거꾸로 뒤집는다
  • 이렇게 되면 시작점은 0, 0이다
• Queue
  • 현재의 칸과 턴수를 가진 Pair 클래스를 가짐
  • 칸 값을 가지고, board상의 위치를 얻음
    • 위치를 통해, 다음 위치의 칸을 얻을 수 있음
    • board상에 위치한 칸의 값이 양수일 경우, 다음 칸이 됨 (ladder, snake)
  • 방문하지 않은 칸이라면, 방문확인용 set에 저장함
• PositionOnBoard
  • 칸 값을 가지고 board상의 위치를 알아낼 수 있음
    • 홀수 행이면, 뒤에서부터 시작되므로
    • c = n-1-c