[백준]16928 뱀과 사다리 게임 - 골드 5

[오늘의 문제]

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

---

[오늘의 학습 키워드]

• 구현, BFS

---

1. 문제설명

 

기존의 뱀과 사다리 게임을 구현하는 문제입니다.

 

1번칸 부터 100번칸 까지 도착하면 게임이 종료되는데 이때 주사위를 최소한으로 굴려 100번칸으로 도착하려 합니다.

첫째 줄에 사다리의 수 N과 뱀의 수 M이 주어지고

그 다음 N개의 줄에 사다리의 이동정보, M개의 줄에는 뱀의 이동정보가 주어집니다.

 

이를 적절히 이용하여 최소한의 주사위 이동을 이용해 100번 칸에 도착하는 방법을 구하는 문제입니다.

---

[제한사항]

• 시간 제한 1초
• 메모리 제한 512MB
• 1 ≤ N ≤ 15
• 1 ≤ M ≤ 15
• 1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다.
• 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다.
• 항상 100번 칸에 도착할 수 있는 입력만 주어진다.

---

2. 접근방식

 

문제를 보자마자 BFS 탐색을 떠올렸습니다.

 

주사위 1부터 6까지의 경우의 수를 모두 queue에 넣어주고 그 때 이동하는 칸의 정보를 queue에 같이 넣어주면 해결이 가능할 것 같습니다.

 

이때 중요한 것은 시간 제한이 1초이니 탐색의 범위 설정이 중요합니다.

 

N과 M이 최대 15개 주어지지만 1번 칸부터 100번 칸까지 이동하는 모든 경우의 수 중 최악의 경우의 수를 고려해 보아야 합니다.

 

기본적으로 탐색시 최대 15개의 사다리 정보조회, 15개의 뱀의 정보 조회, 1번 부터 100번 칸까지의 이동, queue에 저장된 정보를 토대로 이동 등 시간이 오래걸리는 요소가 많습니다.

 

이를 고려하며 중복을 제거하여 queue의 크기를 줄이고 탐색의 범위를 줄이는 방식으로 문제를 해결하였습니다.

---

3. 코드

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

# 입력
N, M = map(int, input().split())
ladders = {}    # 해시 테이블을 이용해 시간 복잡도 O(1) 로 맞추기
snakes = {}

for _ in range(N):
    x, y = map(int, input().split())
    ladders[x] = y
for _ in range(M):
    x, y = map(int, input().split())
    snakes[x] = y
visited = set()

# 시작위치, 주사위 굴린 횟수
queue = deque([(1, 0)])

while queue:
    # 현재 위치, 주사위 굴린 횟수
    location, move = queue.popleft()

    # 종료조건
    if location == 100:
        print(move)
        exit()

    # 다음 이동 위치
    for k in range(1, 7):
        new_location = location + k
        
        # 100 넘으면 할필요 없음
        if new_location > 100:
            continue
        
        # 사다리 확인
        if new_location in ladders:
            new_location = ladders[new_location]
        
        # 뱀 확인
        if new_location in snakes:
            new_location = snakes[new_location]
        
        # 방문처리 후 queue에 넣어주기 방문처리 안되면 중복이니 탐색할 필요 없음
        if new_location not in visited:
            visited.add(new_location)
            queue.append((new_location, move + 1))

---

[코드설명]

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

# 입력
N, M = map(int, input().split())
ladders = {}    # 해시 테이블을 이용해 시간 복잡도 O(1) 로 맞추기
snakes = {}

for _ in range(N):
    x, y = map(int, input().split())
    ladders[x] = y
for _ in range(M):
    x, y = map(int, input().split())
    snakes[x] = y
visited = set()

 

우선 queue를 이용하여 문제를 해결할 건데 앞서 말했듯 시간 복잡도가 1초로 탐색에 비해 시간이 짧은 문제라 최적화가 중요합니다.

 

처음에는 기존의 방식대로 리스트로 입력을 받았다가 매번 사다리와 뱀의 정보를 탐색하는데 시간이 많이 걸려 딕셔너리 형태로 해시 테이블 구조를 이용해 시간 복잡도를 O(1)로 맞춰 주었습니다.

 

딕셔너리 형태로 사다리와 뱀의 정보를 입력 받으니 그에 맞춰 입력을 받고 딕셔너리에 업데이트 해주었습니다.

 

또한 중복 탐색을 방지하기 위해 visited를 생성해 주었는데 마찬가지로 1번칸부터 100번 칸까지 배열로 생성하기 보다는 set을 이용해 중복을 제거하는 방식이 더 로직이 깔끔하고 방문 처리도 쉬워 해당 방식을 이용하였습니다.

---

# 시작위치, 주사위 굴린 횟수
queue = deque([(1, 0)])

while queue:
    # 현재 위치, 주사위 굴린 횟수
    location, move = queue.popleft()

    # 종료조건
    if location == 100:
        print(move)
        exit()

    # 다음 이동 위치
    for k in range(1, 7):
        new_location = location + k
        
        # 100 넘으면 할필요 없음
        if new_location > 100:
            continue
        
        # 사다리 확인
        if new_location in ladders:
            new_location = ladders[new_location]
        
        # 뱀 확인
        if new_location in snakes:
            new_location = snakes[new_location]
        
        # 방문처리 후 queue에 넣어주기 방문처리 안되면 중복이니 탐색할 필요 없음
        if new_location not in visited:
            visited.add(new_location)
            queue.append((new_location, move + 1))

 

BFS 탐색을 실시하기 위해 queue에 최초의 정보를 입력해 주었습니다.

 

1번 칸부터 탐색을 시작할 것이고 그때 주사위를 굴린 횟수는 아직 0회 입니다.

 

queue 입력된 정보를 토대로 주사위를 굴려 다음 이동위치를 결정합니다.

 

현재 위치에 주사위 이동 정보를 더한 새로운 이동정보인 new_location을 선언해 주었는데 

 

새로운 이동 위치에 사다리 혹은 뱀이 있는 경우 무조건 이동해 주어야 합니다. 이를 고려해 이동 위치에 뱀 혹은 사다리가 있는지 확인해 주고, 해당 위치로 바꿔 주었습니다.

 

또한 다음 이동위치가 100을 넘겼다면 더이상 이동할 필요가 없으니 아래 코드를 건너뛰도록 설정해 주었습니다.

 

마지막으로 중복을 제거하기 위해 set으로 선언해 visited 배열을 이용하였습니다.

 

set으로 선언하였기에 추가를 위해서 add를 이용하는데 중복이 없는 경우만 queue에 새로운 이동 정보를 업데이트 하는 방식으로 최적화를 실시하였습니다.

 

종료조건은 역시 이동정보가 100인 경우 주사위를 굴린 횟수를 출력하고 종료해 주었습니다.

---

4. 결과

---

[회고]

처음에는 전부 리스트로 선언하고 매칸을 방문할 때 마다 사다리와 뱀의 정보를 확인해 주었습니다.

 

그러다 최악의 경우를 고려하지 못햇는데 뱀과 사다리가 1개씩 존재하고 이동 위치가 다음칸인 1칸만 이동하는 경우 였습니다.

 

이 경우 뱀과 사다리를 이용하고 최종적으로 100까지 이동하기 위해서는 최대 6칸의 이동을 10회 이상 반복하여야 하는데 중복도 고려하지 않았고, 뱀과 사다리 확인에도 매 칸마다 반복문을 이용해 확인하다 보니 시간초과가 발생하였습니다.

 

단순히 9%에서 시간 초과가 발생하였기에 로직은 맞다 판단 하였고 단순 시간 초과라면 PyPy로 해결이 될 것 같아 PyPy로 돌렸는데 메모리 초과가 발생하였습니다.

 

따라서 최적화를 실시하였습니다.

 

최적화 이전 코드는 리스트 컴프리헨션을 이용해 뱀과 사다리의 정보를 입력받고 매 칸 이동시 반복문을 이용해 뱀과 사다리를 이용하였는데 시간 초과, 메모리 초과가 발생하여 최적화에 많이 고민햇습니다.

 

입력부터 리스트 보다는 해시 테이블 구조를 이용하고자 하였고 단순히 x 에서 y로 이동하는 정보만 주어지기 때문에 딕셔너리 형태를 이용하고자 하였습니다.

 

또한 중복 방문 역시 2차원 배열을 이용해 10 x 10 크기의 리스트를 이용하면 중복탐색이 제대로 이루어지지 않을것 같고 방문처리도 까다로울 것 같아 set을 이용하기로 하였습니다.

 

방문처리에서 확인할 내용은 단순히 해당 칸의 방문 여부이기 때문에 해당 칸의 번호만 존재하면 되었습니다.

 

따라서 set을 이용해 방문처리를 실시하였고 문제를 해결할 수 있었습니다.