[Python] 백준/BOJ 22869번: 징검다리 건너기 (small) (Silver 1)

💻 Problem

문제 보러 가기

 

 N개의 돌이 일렬로 나열되어 있다. N개의 돌에는 왼쪽부터 차례대로 수 A1A2...Ai...AN로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다.

1. 항상 오른쪽으로만 이동할 수 있다.
2.  i번째 돌에서 j(i<j)번째 돌로 이동할 때 (j−i) × (1 + |Ai−Aj|) 만큼 힘을 쓴다.
3. 돌을 한번 건너갈 때마다 쓸 수 있는 힘은 최대 K이다.

이때, 가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는지 구해보자.

 

💡 Approach

이중반복문을 통해 i번째 돌에서 j번째 돌로 이동할 때 드는 힘을 계산한다.

힘이 K 이하이면 이동할 수 있다.

이 정보를 바탕으로 인접 리스트를 만든다.

 

만든 인접 리스트를 이용해 dfs를 돌려 0번째 돌에서 N-1번째 돌까지 이동할 수 있는지 확인한다.

 

✏️ Solution

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

def is_connect(prev):
    if prev == N - 1:
        print("YES")
        exit()
    
    visited[prev] = True
    for next in stones[prev]:
        if not visited[next]:
            is_connect(next)

N, K = map(int, input().split())
A = list(map(int, input().split()))
stones = [[] for _ in range(N)]
visited = [False] * N

for i in range(N):
    for j in range(i + 1, N):
        power = (j - i) * (1 + abs(A[i] - A[j]))
        
        if power <= K:
            stones[i].append(j)

is_connect(0)
print("NO")

인접 리스트 만드는 부분에서 N^2

dfs 탐색에서 노드 수 + 간선 수 = N + N^2

 

둘을 더하면 2 * N^2 + N이다.

N의 최댓값은 5,000이므로 N^2은 약 2 * 10^7이다.