8 분 소요

Graph BFS

문제

문제 링크

You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

  • Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)].
    • This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
  • If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
  • The game ends when you reach the square n2.

A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 do not have a snake or ladder.

Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

  • For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

Return the least number of moves required to reach the square n2. If it is not possible to reach the square, return -1.

Example 1:

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]] Output: 4 Explanation: In the beginning, you start at square 1 (at row 5, column 0). You decide to move to square 2 and must take the ladder to square 15. You then decide to move to square 17 and must take the snake to square 13. You then decide to move to square 14 and must take the ladder to square 35. You then decide to move to square 36, ending the game. This is the lowest possible number of moves to reach the last square, so return 4.

Example 2:

Input: board = [[-1,-1],[-1,3]] Output: 1

Constraints:

  • n == board.length == board[i].length
  • 2 <= n <= 20
  • board[i][j] is either -1 or in the range [1, n2].
  • The squares labeled 1 and n2 do not have any ladders or snakes.

스스로 고민

  • 문제가 뭔 말인지 전혀 모르겠다.
  • Boustrophedon 스타일로 배치되었다는 건 또 뭔소리지

Boustrophedon

텍스트 또는 패턴을 왔다갔다 반복하면서 작성하거나 표시하는 스타일을 나타낸다고 한다. 위 코드에서는 행을 왼쪽에서 오른쪽으로 이동하면서 숫자를 배치한 다음 다음 행에서는 오른쪽에서 왼쪽으로 이동하면서 숫자를 배치한다고 한다. 즉 보드의 행을 번갈아가면서 방향을 바꿔가며 숫자를 배치하는 스타일을 의미한다고 한다.

  • 대충 뱀처럼 지그재그로 숫자가 배치된다는 뜻

  • 벌써부터 어지럽다. 하지만 문제를 차근차근 뜯어보자
  • (언젠가는 이해하겠지….)

접근법

  1. 현재 위치인 curr에서 레이블 범위 [curr + 1, min(curr + 6, n^2)] 내의 목적지 셀 next를 선택. 이 선택은 6면 주사위 던지기를 시뮬레이션한 것으로, 항상 최대 6개의 목적지가 있다. (최대 6칸 간다)
  2. 만약 next가 뱀 또는 사다리가 있는 경우, 해당 뱀 또는 사다리의 목적지로 이동해야 한다. 그렇지 않으면 next로 진행한다.
  3. 게임은 n^2번 셀에 도달할 때 종료된다. (n^2 가 최종 목적지)

게임 보드의 각 셀은 뱀 또는 사다리를 가질 수 있으며, 뱀 또는 사다리가 있는 경우 해당 셀의 값은 -1이 아닌 다른 번호로 표시된다. 단, 1번과 n^2번 셀은 뱀 또는 사다리를 가지지 않는다.

이 게임에서 목표는 최소 이동 횟수를 계산하는 것이며, 만약 목표 셀에 도달할 수 없는 경우 -1을 반환해야 한다.

  • 도저히 이해가 안가니까 예제를 다시 보자
  • 문제에 대한 이해가 아니라 해석 아니 해독을 해야되는 느낌이다.

  • 음~ 이해가 안된다.

    예제 시각화

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]] Output: 4

Explanation: In the beginning, you start at square 1 (at row 5, column 0). You decide to move to square 2 and must take the ladder to square 15. You then decide to move to square 17 and must take the snake to square 13. You then decide to move to square 14 and must take the ladder to square 35. You then decide to move to square 36, ending the game. This is the lowest possible number of moves to reach the last square, so return 4.

보드를 시각화 하면 다음과 같다.

[[-1,-1,-1,-1,-1,-1],
 [-1,-1,-1,-1,-1,-1],
 [-1,-1,-1,-1,-1,-1],
 [-1,35,-1,-1,13,-1],
 [-1,-1,-1,-1,-1,-1],
 [-1,15,-1,-1,-1,-1]]
  • 크기는 6x6 각 셀에는 번호 또는 뱀/사다리 정보가 있다
  • 시작 위치는 (5, 0)이다. (가장 왼쪽 가장 아래)
  • 여기서 다음 이동은 1 부터 6 중에 선택이다.
  • 예제에서 2를 선택했고 (2 칸 이동) 사다리를 타고나서 숫자 15가 있는 곳으로 간다.

  • 숫자 15에서 예제와 같이 17로 이동한다면 (오른쪽으로 2번 이동) 뱀을 따라 숫자 13번 타일로 이동한다.
  • 여기서 오른쪽으로 이동 1을 하면 숫자 타일 14로 가고 14에서 사다리를 타고 35로 올라간다.
  • 35에서 36으로 가면 게임은 끝난다.

  • 근데 이 문제를 어떻게 풀지….
  • 우선 지그재그로 계속 바뀌기 때문에 탈출지점이 왼쪽 상단인지 오른쪽 상단인지부터 조건 검사를 시작해야 될 것 같다.
  • 그 후 bfs를 이용해서 풀어보려고 한다.

  • 하지만 도저히 못 풀겠어서 다른 사람 풀이를 보고 공부하기로 했다.
  • 아직 그래프에 대한 이해를 갖고 풀이를 똑바로 못 하는 것 같다….

구현 코드

from collections import deque

def snakesAndLadders(board):
    n = len(board)
    target = n * n
    
    def get_coordinates(num):
        # 숫자를 좌표로 변환하는 함수
        row = n - 1 - (num - 1) // n
        col = (num - 1) % n if (num - 1) // n % 2 == 0 else n - 1 - (num - 1) % n
        return row, col
    
    visited = set()
    queue = deque([(1, 0)])  # 시작 위치와 이동 횟수
    visited.add(1)
    
    while queue:
        num, moves = queue.popleft()
        
        if num == target:
            return moves
        
        for i in range(1, 7):
            next_num = num + i
            if next_num > target:
                break
            
            row, col = get_coordinates(next_num)
            
            # 보드에 있는 숫자를 확인하고 이동
            if board[row][col] != -1:
                next_num = board[row][col]
            
            if next_num not in visited:
                queue.append((next_num, moves + 1))
                visited.add(next_num)
    
    return -1  # 목적지에 도달할 수 없는 경우

# 예제 테스트 케이스
board = [[-1,-1,-1,-1,-1,-1],
         [-1,-1,-1,-1,-1,-1],
         [-1,-1,-1,-1,-1,-1],
         [-1,35,-1,-1,13,-1],
         [-1,-1,-1,-1,-1,-1],
         [-1,15,-1,-1,-1,-1]]

result = snakesAndLadders(board)
print(result)  # 출력: 4

해독

  • 우선 보드판을 구상해야된다. 리스트 형식으로 받아오니 len 함수로 사이즈가 어떻게 되는지 확인한다.
  • 근데 생각해보니 어차피 마지막 번호를 찾아가는거니까 n x n 이 탈출구다. 오른쪽이든 왼쪽이든 상관이 없다. 어차피 숫자로 찾아가니깐
  • 그렇다면 왼쪽 오른쪽 지그재그로 숫자 나열이 되는건 어떻게 해결해야되는지 생각해보자.
  • 다른 사람의 풀이에서는 아래와 같이 좌표를 만들었다.
    def get_coordinates(num):
        # 숫자를 좌표로 변환하는 함수
        row = n - 1 - (num - 1) // n
        col = (num - 1) % n if (num - 1) // n % 2 == 0 else n - 1 - (num - 1) % n
        return row, col
  • 이전에도 탐색 문제에 대해서는 좌표를 만들고 그 좌표를 하나하나 탐색하는 논리였다.
  • 탐색 문제가 나오면 위와 같이 좌표부터 만드는 패턴을 익혀야 될 거 같다.
  • 근데 그래서 저게 무슨 논리지?
  • 이해가 안되서 처음부터 차근차근 생각해봤다.
[[-1,-1,-1,-1,-1,-1],
 [-1,-1,-1,-1,-1,-1],
 [-1,-1,-1,-1,-1,-1],
 [-1,35,-1,-1,13,-1],
 [-1,-1,-1,-1,-1,-1],
 [-1,15,-1,-1,-1,-1]]
  • 지금 예제에서 n 은 6이다. 그리고 처음 시작은 [-1,-1,-1,-1,-1,-1] 이다.
  • 일단 위에 정의된 함수를 호출해서 다시 부르니까 그 다음 코드를 보고 다시 생각해보자
    visited = set()
    queue = deque([(1, 0)])  # 시작 위치와 이동 횟수
    visited.add(1)

visited는 내가 방문한 기록을 넣고 set()은 중복을 없앤다.
1,0 에서 1은 처음 시작위치 0은 이동횟수로 초기화 시킨다.
1에서 시작했고 여기는 탐색 되었으니 visited에 1을 추가한다.

    while queue:
        num, moves = queue.popleft()
        
        if num == target:
            return moves
        
        for i in range(1, 7):
            next_num = num + i
            if next_num > target:
                break
            
            row, col = get_coordinates(next_num)
            
            # 보드에 있는 숫자를 확인하고 이동
            if board[row][col] != -1:
                next_num = board[row][col]
            
            if next_num not in visited:
                queue.append((next_num, moves + 1))
                visited.add(next_num)
    
    return -1  # 목적지에 도달할 수 없는 경우

queue가 비어있지 않으면 계속 진행된다.
이전에 queue에는 (1,0)이 있으니 num은 1 (좌표) moves 는 0 (이동거리) 가 뽑힌다.

주사위는 1부터 6이이고 주변탐색을 위해 range(1,7) 까지 진행한다.
주사위가 1일 경우부터 시작!
next_num 값은 현재 num = 1 + 1
next_num은 2다.
해당 좌표가 현재 타겟과 맞으면 종료
그렇지 않을 경우 row와 col를 반환하는 get_coordinates 함수가 호출된다. 그럼 아까 이해가 되지 않았던 부분을 다시 불러와보자.

    def get_coordinates(num):
        # 숫자를 좌표로 변환하는 함수
        row = n - 1 - (num - 1) // n
        col = (num - 1) % n if (num - 1) // n % 2 == 0 else n - 1 - (num - 1) % n
        return row, col

next_nums = 2 고 num에 2가 들어온다.
row 는 n= 6 == > row = 6 - 1 - (6 - 1) // 6 ==> 5 - 5 // 2 ==> 0//2 row 는 0이 된다. col = (2 - 1) % 6 if (2 - 1) // 2 % 2 == 0 else 6 - 1 - (2 - 1) % 6
뭔가 복잡한데 삼항연산자로 우선

  • (num - 1) % n은 숫자를 열로 나눈 나머지를 구한다. 이렇게 하면 해당 숫자가 몇 번째 열에 있는지 알 수 있다.
  • (num - 1) // n % 2 == 0은 현재 행 번호가 짝수 행인지 확인한다. 짝수 행에서는 좌에서 우로 이동하고 홀수 행에서는 우에서 좌로 이동하므로, 이를 기준으로 열 번호를 조정한다. (지그재그로 움직이니깐! )
789
654
123

- 이래서 아까 삼항연산자로 좌표를 다르게 뽑은 거였다.
- 드디어 이해했다 ㅜ

  • 만약 현재 행 번호가 짝수 행이라면, (num - 1) % n 값을 그대로 사용하고, 홀수 행이라면 n - 1 - (num - 1) % n 값을 사용하여 열 번호를 역순으로 변환한다.

위와 같은 논리로 row와 col를 반환한다.

            # 보드에 있는 숫자를 확인하고 이동
            if board[row][col] != -1:
                next_num = board[row][col]
            
            if next_num not in visited:
                queue.append((next_num, moves + 1))
                visited.add(next_num)

row 와 col이 반환 되었을 때 board 에 좌표 값으로 사다리나 뱀이 있는지 확인한다. -1이 아닐 경우 사다리나 뱀을 만난 경우이므로 해당 좌표로 이동하고 그 값을 next_num에 넣어준다.

뱀이나 사다리를 만난 경우 next_num의 값은 변했고 만약 만나지 않았을 경우는 초기 값 그대로 2다. (nums 는 현재 밟고 있는 숫자 타일이다.)

만약 방문한 곳에 next_num (밟고 있는 숫자 타일) 값이 없다면 큐에 next_nums 와 moves +1 로 현재 위치와 이동 거리를 업데이트 해주고 방문한 곳에 현재 위치를 반영해준다.

만약 방문한 적이 있다면?
기존 while 문이 돌아가면서 주사위 2가 나왔을때의 3 숫자 타일로 진행된다.

위와 같은 로직으로 현재위치 num 이 target 위치가 맞았을 때 움직인 횟수를 리턴하며 그렇지 않고 모든 경우를 방문한 뒤에 큐가 비게 된다면 -1을 리턴한다.

시간 복잡도와 공간 복잡도

시간 복잡도:

  • 최악의 경우, 모든 가능한 이동 경로를 탐색하기 위해 BFS를 사용하므로 시간 복잡도는 O(n^2) 다. 여기서 n은 보드의 한 변의 길이다.

공간 복잡도:

  • 공간 복잡도는 큐에 저장된 노드의 개수와 방문한 노드를 기록하기 위한 visited 세트의 크기에 의해 결정된다.
  • 큐에 저장된 노드의 개수는 BFS의 각 단계에서 방문하는 노드의 수에 따라 달라진다. 최악의 경우, 모든 가능한 이동 경로를 탐색해야 하므로 최대 n^2 개의 노드가 큐에 저장될 수 있다.
  • visited 세트는 보드 위의 모든 위치에 대한 방문 여부를 기록하므로 n^2 개의 항목을 가진다.
  • 따라서 공간 복잡도는 O(n^2) 다.

회고 과정

  • 솔직히 다른 사람이 풀어 놓은 코드도 보자마자 바로 이해를 못 하는 수준인데 문제를 계속 푸는 게 맞을까?
  • 그냥 개념 공부를 더 해야하는 게 맞는걸까…?
  • 뭐가 좋을지 모를 때는 그냥 둘 다 하면 된다.
  • 개념 공부 1시간 문제 풀이 하루에 딱 1개씩만 꾸준히 해보자

댓글남기기

참고