BOJ 16928. [Gold5] 뱀과 사다리 게임

[hojongs]

Problem link

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

Problem abstraction

문제의 핵심을 요약한다. 체계적인 문제 접근을 위해, 문제를 추상화한다

적합한 자료구조를 생각한다

Design(Plan) algorithm

# 1

---
# 2

---
# 3

Algorithm idea

추상화한 문제 이해를 기반으로 알고리즘의 대략적인 구현 계획을 서술한다

DP?인가 했으나 알고리즘을 글로 작성하다보니 BFS였음

Pseudo-code

idea를 수도 코드로 작성해본다

파이썬 코드와 거의 동일

Validate algorithm

알고리즘의 유효 여부를 구현 전에 검증한다

예제 입력을 수도 코드로 계산해보고, 놓친 알고리즘 오류가 있는지 확인한다

제출 후 메모리 초과 발생 -> snake(이전으로 돌아감)이 존재하므로 재방문 하지 않도록 함

Impl

import sys
from collections import deque

readl = sys.stdin.readline


def f():
    n, m = map(int, readl().split())
    ladder_snakes = [[int(i) for i in readl().split()] for _ in range(n+m)]
    visited = [0] * 101
    visited[1] = 1
    # 1칸에서 시작한다
    # BFS로 순회한다 (가장 먼저 도착하는 것)
    # 각 아이템은 (현재 위치, 주사위 굴린 수)로 구성된다
    queue = deque([[1, 0]])
    while queue:
        curr_pos, dice_cnt = queue.popleft()
        if curr_pos == 100:
            print(dice_cnt)
            break
        visited[curr_pos] = 1
        for from1, to1 in ladder_snakes:
            if from1 == curr_pos:
                curr_pos = to1
                visited[curr_pos] = 1
                break
        for dist in range(1, 6+1):
            if curr_pos+dist > 100:
                break
            if visited[curr_pos+dist] == 0:
                visited[curr_pos+dist] = 1
                queue.append([curr_pos+dist, dice_cnt+1])


f()

Self-feedback

구조적 접근: 문제를 추상화하여 구조적으로 접근했는가?

사고력: 알고리즘을 완전히 이해했는가? (충분한 사고력을 가졌는가?)

구현력: 알고리즘을 신속, 정확하게 구현했는가?