99클럽 코테 스터디 18일차 TIL + BFS

문제

Baekjoon 27971: 강아지는 많을수록 좋다

• 설명: 호무라가 강아지를 한번에 A, B 마리를 생성할 수 있고 특정 구간의 강아지 수를 만족한다면 모든 강아지는 사라진다. 이떄 N마리의 강아지를 생성하기 위한 최소 마법의 수를 구하여라

풀이

• 닫힌 구간을 미리 모두 저장해두고 A, B마리를 생성해주며 시뮬레이션 해준다.
• 이떄 가장 최소 마법의 수를 구하는 문제이기 떄문에 BFS를 사용하여 문제를 풀어준다.

오늘의 회고

• True를 False로 두는 둥 잔실수가 많았다. 더 노력하자!

Code

# Baekjoon27971.py
import sys
input = sys.stdin.readline

from collections import deque

n, m, a, b = map(int, input().split())
delete = [False for _ in range(100_001)]

for _ in range(m):
    l, r = map(int, input().split())

    for i in range(l, r + 1):
        delete[i] = True

q = deque()
visited = [False for _ in range(100_001)]

q.append((0, 0))
visited[0] = True

ans = -1
while q:
    curr, time = q.popleft()
    if curr == n:
        ans = time
        break

    next_dog = curr + a
    if next_dog <= 100_000 and (not visited[next_dog]) and (not delete[next_dog]):
        visited[next_dog] = True
        q.append((next_dog, time + 1))

    next_dog = curr + b
    if next_dog <= 100_000 and (not visited[next_dog]) and (not delete[next_dog]):
        visited[next_dog] = True    
        q.append((next_dog, time + 1))

print(ans)

필수 해시태그: # #코딩테스트준비 # # #