[백준] 27971번 강아지는 많을수록 좋다

문제링크: https://www.acmicpc.net/problem/27971

아이디어

한 번에 A 혹은 B step 만큼 이동할 수 있다. 현재 위치에서 BFS로 탐색하되, 현재 위치+A 혹은 현재 위치+B의 값을 업데이트하며 목적지에 도달

코드

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

class magic():
    def __init__(self, magic_a: int = 0, magic_b: int = 0, restrictions=None) -> None:
        self.magic_a = magic_a
        self.magic_b = magic_b
        self.restriction = []
        if restrictions != None:
            for interval in restrictions:
                self.restriction.extend(
                    [i for i in range(interval[0], interval[1]+1)])
        self.restriction = set(self.restriction)

    def make_puppy(self, target: int = 0) -> int:

        visited = [False] * (target+1)
        for res in self.restriction:
            visited[res] = True

        queue = deque()
        queue.append((0, 0))
        visited[0] = True
        while queue:
            cur_puppy, action_cnt = queue.popleft()
            if cur_puppy == target:
                return action_cnt

            for nxt in [cur_puppy+self.magic_a, cur_puppy+self.magic_b]:
                if nxt <= target and not visited[nxt]:
                    visited[nxt] = True
                    queue.append((nxt, action_cnt+1))
        return -1


def init_data():
    total_puppy, total_interval, magic_a, magic_b = map(int, input().split())
    intervals = [list(map(int, input().split()))
                 for _ in range(total_interval)]

    return magic(magic_a, magic_b, intervals), total_puppy


if __name__ == '__main__':
    magic_info, puppy = init_data()
    print(magic_info.make_puppy(puppy))

결과