[백준] 16928번 뱀과 사다리 게임 - (Python)

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

16928번: 뱀과 사다리 게임

BFS를 이용하여 구현하는 문제. 그러나, 구현방식을 생각하지 못했습니다. 뱀과 사다리를 처리하는 방법을 생각하지 못해, 풀이를 참고해서 제 방식대로 구현했습니다.

먼저, 각각의 보드판에 이동 횟수를 저장하고, 방문여부와 뱀과 사다리를 적절하게 구현하여, BFS를 구현하면 됩니다. 해당 내용은 아래에서 설명하겠습니다.

 

※ 고려 사항

1. 뱀, 사다리 처리

2. BFS

---

1. 뱀, 사다리 처리

이 방식을 구현하지 못해서 문제를 해결하지 못했습니다. 여기서 핵심은 사다리와 뱀을 각각 dict 자료구조를 사용하여, key, value 값으로 저장하는 것입니다.

dict을 사용하는 이유는 현재위치가 해당 key값과 동일한 경우 value에 해당하는 값을 현재위치에 다시 대입하여 위치를 최신화할 수 있기 때문에 dict를 이용하는 것이 효율적입니다. 코드는 다음과 같습니다.

import sys
from collections import deque

input = sys.stdin.readline

# 1 ~ 100번 칸 방문횟수
matrix = [0] * 101

# 방문 여부
visited = [False] * 101

# 사다리, 뱀 개수 입력
n, m = map(int, input().split())

ladder = dict()
snake = dict()

for _ in range(n):
    a, b = map(int, input().split())
    ladder[a] = b

for _ in range(m):
    a, b = map(int, input().split())
    snake[a] = b

 

2. BFS

여기서는 조건문만 잘 구현해 주면 기존 BFS구현방식과 동일합니다.

현재위치에서 각각 주사위를 1부터 6까지를 더하고 해당 위치에서 발생하는 모든 경우를 생각해 줍니다. 단, 해당 index를 벗어나면 안 되기 때문에 범위 내에서 방문되지 않았는지 유무를 판단해 줍니다.

 

또 뱀과 사다리를 만났다면 해당 key에 해당하는 value값으로 현재위치를 최신화해줍니다. 만약, 뱀과 사다리가 없다면, 해당위치 + 1을 한 값을 queue에 다시 삽입하여, 해당 위치에서 다시 주사위를 굴릴 수 있도록 합니다.

+ 1을 하는 이유는 기존 위치에서 주사위를 굴렸기 때문에 그 횟수를 증가해 줍니다. 코드는 다음과 같습니다.

def bfs():
    queue = deque([1])

    while queue:
        v = queue.popleft()

        # 100에 도착하면 방문횟수 출력
        if v == 100:
            print(matrix[v])
            break

        for dice in range(1, 7):
            # 다음 이동할 위치
            place = dice + v
            
            # 범위안에서 방문되지 않았다면
            if place <= 100 and visited[place] == False:
                
                # 사다리를 만났다면 위치변경
                if place in ladder.keys():
                    place = ladder[place]
                
                # 뱀을 만났다면 위치변경
                if place in snake.keys():
                    place = snake[place]
                
                # 뱀과 사다리가 없다면, 방문처리
                if visited[place] == False:
                    visited[place] = True
                    matrix[place] = matrix[v] + 1
                    queue.append(place)

---

전체코드

import sys
from collections import deque

input = sys.stdin.readline

# 1 ~ 100번 칸 방문횟수
matrix = [0] * 101

# 방문 여부
visited = [False] * 101

# 사다리, 뱀 갯수 입력
n, m = map(int, input().split())

ladder = dict()
snake = dict()

for _ in range(n):
    a, b = map(int, input().split())
    ladder[a] = b

for _ in range(m):
    a, b = map(int, input().split())
    snake[a] = b

def bfs():
    queue = deque([1])

    while queue:
        v = queue.popleft()

        # 100에 도착하면 방문횟수 출력
        if v == 100:
            print(matrix[v])
            break

        for dice in range(1, 7):
            # 다음 이동할 위치
            place = dice + v
            
            # 범위안에서 방문되지 않았다면
            if place <= 100 and visited[place] == False:
                
                # 사다리를 만났다면 위치변경
                if place in ladder.keys():
                    place = ladder[place]
                
                # 뱀을 만났다면 위치변경
                if place in snake.keys():
                    place = snake[place]
                
                # 뱀과 사다리가 없다면, 방문처리
                if visited[place] == False:
                    visited[place] = True
                    matrix[place] = matrix[v] + 1
                    queue.append(place)

bfs()

---

그래프 문제를 어느 정도 이해했다고 생각했는데, 문제의 조건이 까다롭고 구현방식이 많아지다 보니, 해결하지 못했습니다. 골드정도 난이도가 되니, 구현 방식도 다양하게 생각할 필요성을 느꼈습니다. 

설명의 오류나, 궁금하신 점은 언제든 피드백해주시면 감사하겠습니다 ^~^