🥚문제

https://www.acmicpc.net/problem/16928

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline
from collections import deque

def num_to_row_col(n):
    # n번 칸 -> 몇번째 행, 몇번째 열에 위치하는지 리턴
    if n % 10 == 0:
        row = n // 10 - 1
        col = 9
    else:
        row = n // 10
        col = (n % 10) - 1
    return row, col

def row_col_to_num(r, c):
    if c == 9:
        return (r+1)*10
    
    return r*10 + (c+1)

def bfs():
    q = deque([(0, 0, 0)])
    visited = [[False]*10 for _ in range(10)]
    visited[0][0] = True

    while q:
        r, c, cnt = q.popleft()
        num = row_col_to_num(r, c)

        if num == 100:
            return cnt

        for i in range(1, 7):
            new_num = num + i
            
            if new_num > 100:
                break
            
            new_r, new_c = num_to_row_col(new_num)

            if not visited[new_r][new_c]:
                if board[new_r][new_c] == 0:
                    q.append((new_r, new_c, cnt + 1))
                    visited[new_r][new_c] = True
                else:
                    # 뱀이나 사다리 칸일 때

                    # 다른 뱀이나 사다리칸을 만나지 않을 때까지 반복한다
                    while board[new_r][new_c] != 0:
                        # new_r, new_c 방문 표시!
                        visited[new_r][new_c] = True
                        # 이동해야하는 move_r, move_c
                        move_r, move_c = board[new_r][new_c]
                        # 업데이트
                        new_r, new_c = move_r, move_c
                    
                    # 마지막으로 도달한 칸을 q에 추가해준다
                    q.append((new_r, new_c, cnt + 1))

board = [[0]*10 for _ in range(10)]
N, M = map(int, input().split())
# 사다리
for _ in range(N):
    x, y = map(int, input().split())
    x_row, x_col = num_to_row_col(x)
    y_row, y_col = num_to_row_col(y)
    board[x_row][x_col] = (y_row, y_col)
# 뱀
for _ in range(M):
    u, v = map(int, input().split())
    u_row, u_col = num_to_row_col(u)
    v_row, v_col = num_to_row_col(v)
    board[u_row][u_col] = (v_row, v_col)

ans = bfs()
print(ans)

---

🧂아이디어

BFS

• BFS를 이용하여 간단하게 풀 수 있었던 문제

• 보드판은 10*10 리스트로 만들어주었다. 일반 칸은 board[r][c] = 0으로 표시해주었고 뱀이나 사다리칸은 board[r][c] = (이동할row, 이동할col) 값으로 표시했다.

• 항상 숫자로 칸의 번호가 주어지므로 이를 행, 열로 변환해주는 함수 num_to_row_col와
  행, 열을 다시 칸의 번호로 변환해주는 함수 row_col_to_num을 작성했다.

• bfs를 할 때, 큐에는 (행, 열, 주사위 던진 횟수)를 저장한다.

• 현재 위치한 칸의 번호인 num에서 1부터 6까지를 더하며 주사위를 던졌을 때 이동할 수 있는 곳으로 각각 BFS를 한다.
  • 단, num+x(1<=x<=6)이 100보다 커지면 중단한다.

• 주사위를 던져서 이동한 곳의 좌표를 new_r, new_c라고 한다.

• board[new_r][new_c] == 0 이면 일반 칸이므로 방문표시를 해주고, 큐에 (new_r, new_c, 주사위횟수 + 1)을 저장한다.

• board[new_r][new_c] != 0 이면 뱀/사다리 칸이다.
  • 이때, 뱀/사다리칸으로 이동했을 때 또 뱀/사다리칸일 가능성이 있다.
  • 따라서 뱀/사다리칸이 아닌 칸에 도달할 때까지 while문을 통해 계속 확인해줘야 한다.
  • 확인하면서 방문하는 모든 칸들을 방문표시해준다.
  • 뱀/사다리칸이 아닌 칸(new_r, new_c)에 도착하게 되면 큐에 (new_r, new_c, 주사위횟수 + 1)을 저장한다.

• BFS를 하다 100번째 칸에 도달하게 되면 지금까지 굴린 주사위 횟수인 cnt를 리턴한다!