[Python] 백준 22869 징검다리 건너기 small (BFS/DP)

선주·2022년 2월 4일

Python PS

목록 보기

38/65

📌 문제

$N$ 개의 돌이 일렬로 나열 되어 있다. $N$ 개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$ 로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다.

항상 오른쪽으로만 이동가능하다.
$i$ 번째 돌에서 $j(i < j)$ 번째 돌로 이동할 때 $(j - i)$ × (1 + | $A_{i} - A_{j}$ |) 만큼 힘을 쓴다.
돌을 한번 건너갈 때마다 쓸 수 있는 힘은 최대 $K$ 이다.
이때, 가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는지 구해보자.

입력

첫 번째 줄에 돌의 개수 $N$ 와 쓸 수 있는 최대 힘 $K$ 가 공백으로 구분되어 주어진다.

두 번째 줄에는 $N$ 개의 돌의 수 $A_i$ 가 공백으로 구분되어 주어진다.

출력

가장 오른쪽에 있는 돌로 이동할 수 있다면 YES를 출력한다. 만약 이동하지 못하는 경우에는 NO를 출력한다.

제한

$2 \le N \le 5,000$
$1 \le K \le 1,000$
$1 \le A_{i} \le 1,000$

예제 입력 1

5 3
1 4 1 3 1

예제 출력 1

YES

예제 입력 2

5 3
1 5 2 1 6

예제 출력 2

NO

📌 풀이

💬 BFS Code

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

n, k = map(int, input().split())
stone = list(map(int, input().split()))
reached = [0 for _ in range(n)]

q = deque([0])
reached[0] = 1
while q:
    a = q.popleft()
    for b in range(a + 1, n):
        if (b - a) * (1 + abs(stone[a] - stone[b])) <= k and not reached[b]:
            reached[b] = 1
            q.append(b)
            if b == n - 1:
                print('YES')
                sys.exit(0)

print('NO')

💡 BFS Solution

reached[x] : 돌 x에 도달할 수 있으면 1, 없으면 0을 저장

일단 시작점은 0번째 돌이므로 a = 0이 된다. a에서 출발해 b에 도달할 수 있는지 체크할 것이기 때문에 b는 1부터 n-1이 된다.

a에서 b로 갈 때의 힘을 계산해서 k보다 작으면 b에 도달할 수 있는 것이다. 따라서 reached[b]를 1로 갱신할 것인데, 이미 reached[b]가 1이면 b에 도달할 수 있다는 사실을 진작에 알고 있다는 것이므로 이 갱신작업을 또 해줄 필요가 없다. 그래서 not reached[b] 조건을 더해준 것이다.

아무튼 갱신을 완료하면 이 b에서 출발해서 도달할 수 있는 곳도 체크해주기 위해서 q.append(b)를 해준다.

큐에 탐색할 돌이 남아있으면 계속 이 작업을 반복 수행하는데, 만약 b == n - 1이면 마지막 돌에 도달할 수 있다는 것이니 YES를 출력하고 종료한다.

~~(나는 YES를 Yes로, NO를 No로 출력하도록 작성해서 한시간동안 맞왜틀;;;;; 하고 있었삼 ^_ㅠ 하다하다 이런 실수도 하고 쩝 눈 똑바로 뜨고 풀자.....)~~

💬 DP Code

n, k = map(int, input().split())
stone = list(map(int, input().split()))
dp = [0] * N
dp[0] = 1

for i in range(n - 1):
    for j in range(i + 1, n):
        if dp[i] and (j - i) * (1 + abs(stone[j] - stone[i])) <= k:
        	dp[j] = 1

print("YES" if dp[n - 1] else "NO")