백준 - 16928 뱀과 사다리 게임

이번 문제는 '뱀과 사다리 게임'이라는 문제인데 해당 게임은 어렸을 때 몇 번 해본 기억이 난다. 

아래에서 맨 꼭대기로 올라가는 문제인데 중간 중간 사다리나 뱀을 타고 올라가기도 내려가기도 했던 게임

 

대충 이런 모양

여기서 우리는 1~6의 값을 가진 주사위를 최소 몇 번 던져서 도착 지점에 갈 수 있는지 구해야 한다.

그리고 어떤 발판은 사다리로 더 멀리 있는 지점에 도달할 수 있고 어떤 발판은 뱀으로 다시 내려오기도 한다.

 

어떠한 경로를 최소 단계로 도달한다? -> BFS일 것이라고 생각했다.

 

DFS의 경우에는 불가능한 수로 너무 깊게 빠질 수 있으므로 최소 단계를 구하는 데는 적합하지 않다.

+ 깊이에 따라 스택 오버플로가 발생할 수도 있고

 

또한 단순히 위 게임의 그림을 보고 발판을 10 X 10의 2차원 배열로 선언할 수도 있겠지만

사실 이 게임은 단순히 앞과 뒤로만 움직이기 때문에 1차원 구조라고 할 수 있다.

 

따라서 순회하기 위한 보드는 1차원으로 선언하고 마찬가지로

이미 거쳤던 노드인지 확인하는 visit도 1차원으로 선언하면 된다.

 

이미 거쳤는지 확인하는 이유는

최소 횟수를 구하는 상황에서 한 발 늦은 경우를 의미하므로 필요없는 수이기 때문이다.

 

그리고 보드 초기화 시 모든 노드의 값을 자기 칸 수(첫번째 칸이면 0, 두번째면 1, ...)로 초기화하고

그 칸이 사다리면 자신이 올라갈 칸으로

그 칸이 뱀이면 자신이 내려갈 칸으로 값을 변경하면

해당 노드에 도착시 뱀인지 사다리인지 일반 칸인지 확인하지 않더라도 칸의 값에 따라 알아서 움직이게 구현할 수 있다.

 

풀이

from collections import deque


def dfs():
    N, M = map(int, input().split(" "))

    board = [i for i in range(100)]
    visit = [0 for _ in range(100)]

    for i in range(N):
        x, y = map(int, input().split(" "))
        board[x - 1] = y - 1

    for i in range(M):
        u, v = map(int, input().split(" "))
        board[u - 1] = v - 1

    q = deque()
    q.append(0)

    steps = 0
    while q:

        for i in range(len(q)):
            now = q.popleft()
            visit[now] = 1

            if now == 99:
                return steps

            for dice in range(1, 7):
                if now + dice > 99 or visit[board[now + dice]]:
                    continue

                q.append(board[now + dice])

        steps += 1

    return -1


print(dfs())

참고로 파이썬의 언패킹 구문을 이용하면 

쉽게 공백을 기준으로 두 변수에 입력값을 각각 넣어 줄 수 있다.