[알고리즘] 백준 16928번 : 뱀과 사다리 게임

백준 16928번 : 뱀과 사다리 게임
난이도 : 골드 5

- 문제 소개

- 조건

• 없음

- 코드

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

n, m = map(int, input().split())
graph = [0] * 101
visited = [False] * 101

ladders = {}
snakes = {}

for _ in range(n):
    x, y = map(int, input().split())
    ladders[x] = y

for _ in range(m):
    u, v = map(int, input().split())
    snakes[u] = v

def bfs():
    q = deque([1])
    visited[1] = True
    while q:
        now = q.popleft()
        for i in range(1, 7):
            check_move = now + i
            if 0 < check_move <= 100 and not visited[check_move]:
                if check_move in ladders.keys():
                    check_move = ladders[check_move]
                if check_move in snakes.keys():
                    check_move = snakes[check_move]
                if not visited[check_move]:
                    q.append(check_move)
                    visited[check_move] = True
                    graph[check_move] = graph[now] + 1

bfs()
print(graph[100])

- 해설

뱀과 사다리 게임 설명

처음 입력되는 수는 사다리의 개수, 뱀의 마릿수입니다.
그 다음 입력되는 것은 사다리의 위치와 이동하는 위치, 뱀의 위치와 이동하는 위치가 주어집니다. 여기서 입력되는 사다리의 값과 뱀의 값이 굉장히 중요하므로 딕셔너리 구조를 이용해서 저장해주었습니다. 문제에선 10 * 10의 정사각형 구조라고 했지만, 이를 쉽게 표현하면 100칸짜리 배열이라고 생각할 수 있었습니다. 위에서 입력되는 사다리, 뱀의 좌표와 일치하기 위해서 101칸짜리 배열을 만들어주었고, 방문했는지를 체크하기 위한 visited 배열도 101칸으로 만들었습니다. 그 다음 일직선으로 쭉 타고 가기 위해서 BFS를 통해 문제를 풀었는데요, 첫 번째 칸(graph[1])부터 이동해야하므로 q = deque([1]) 선언, visited[1]=True로 선언해주고 while문을 돌아줍니다. 돌면서 for i in range(1, 7):라는 반복문을 만나는데요, 이는 정육면체 주사위 1~6을 돌아보는 역할입니다. 그러면서 나온 값과 현재 값을 더해서 check_move라는 값을 만들어주고, 이것이 범위 내에 있고 방문한 적이 없으면 다음 조건을 체크합니다. 다음 조건은 check_move의 위치에 사다리가 있는지, 뱀이 있는지를 확인하는 겁니다. 사다리의 위치에 있으면 사다리 끝 지점으로 이동하고, 뱀의 위치에 있으면 뱀의 끝 지점으로 이동합니다. 그렇게 이동한 지점이 방문한 적이 없다면 큐에 넣어주고 방문했다고 표시합니다. 그리고 몇 번 이동했는지 확인하기 위해 graph[check_move] = graph[now] + 1을 해줍니다.