[백준] 16928번 뱀과 사다리게임 -python 파이썬

문제

 

 

이 문제를 딱 보는 드는 생각은 변형된 미로 문제 같다는 생각이다. 뱀과 사다리와 같은 요소가 추가되긴 했지만 본질은 미로에서 최단경로 찾기와 같다. 

 

그렇기 때문에 BFS를 사용해서 문제를 풀어주었다.

 

 

이 문제의 까다로운 점은 뱀과 사다리 요소의 처리, 그리고 입력값이 2차원 배열에 맞게 주어지지 않는다는 것이다. 거기다가 0부터 시작이 아닌 1부터 시작이기때문에 이에 대한 처리도 해주어야한다.

 

이때 나는 입력값-1 한 것을 인덱스로 변환해주는 방법을 선택했다. 나중에 처리하게되면 값을 사용할 때마다 처리를 해주어야돼서 복잡해지기 때문에 입력값-1을 해준 후 10의 자리는 1의자리를 그대로 활용해서 인덱스로 써주었다.

코드

from collections import deque
n, m = map(int, input().split())
board = [[0] * 10 for _ in range(10)]
#사다리와 뱀을 저장하는 배열
ss = [[0] * 10 for _ in range(10)]

for _ in range(n):
    x, y = map(int, input().split())
    x-=1
    y-=1
    i = x // 10
    j = x % 10
    ss[i][j] = y
for _ in range(m):
    x, y = map(int, input().split())
    #0~99로 바꾸어줌
    x-=1
    y-=1
    i = x // 10
    j = x % 10
    ss[i][j] = y

def bfs(board,ss):
    q = deque()
    q.append((0,0))

    while(q):
        a,b = q.popleft()
        x = 10 * a + b
        for i in range(1,7):
            #nxt는 주사위를 굴려서 갈 다음 칸
            nxt = x+i
            u = nxt // 10
            v = nxt % 10
            if 0<=u<10 and 0<=v<10:
                #사다리나 뱀이 있는 칸이라면
                if ss[u][v] != 0:
                    #이동해야되는 칸의 정보 nxt에 저장
                    nxt = ss[u][v]
                    u = nxt // 10
                    v = nxt % 10
                #nxt칸이 아직 방문한 적 없고 범위내에 있다면 
                if 0<=u<10 and 0<=v<10 and board[u][v] == 0:
                    board[u][v] = board[a][b] + 1
                    q.append((u,v))

bfs(board,ss)
print(board[9][9])

 

 

일단 다음칸을 확인하는 것을 1~6까지 도는 for문을 통해서 해주었다.

 

이때 뱀이나 사다리가 없는 칸이라면 nxt = x+i가 되지만 있는 칸이라면 미리 저장해두었던 값을 2차원 배열의 인덱스형태로 변환해주어 다음 위치로 지정해주었다.

 

평소 미로 문제의 상하좌우로 이동하던 것을 주사위+뱀,사다리 이동형태로 변환해주는 것이 중요한 포인트였던 문제였던 것 같다.