17260

17260번 계곡이 넘쳐흘러

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	627	149	105	25.672%

지문 분석

• 그래프(트리) 문제.
  • 계곡 = 정점, $n(V) = N \leq 200,000$)
  • 물길 = 간선, $n(E) = N-1$
  • 지문에서 그래프는 트리임을 시사한다.
  • 각 계곡(정점)는 높이가 있다.
  • 물은 높은 곳에서 낮은 곳으로만 흐른다.
  • 두 계곡에서 흐른 물은 두 계곡의 높이 차의 절반만큼 튀어 오른다.
    • 정점 $u$에서 물의 높이가 $h$일 때, 간선 $u \to v$를 선택한 후의 물 높이 $h’ = \frac{h+H_v}{2}$
• 요구사항
  • $K$를 제외한 임의의 정점 $u$에서 높이 $H_u$로 시작한 물 줄기가 $K$번째 정점까지 도달할 있는 $u$가 존재하는지 여부를 출력. (1 or 0)
  • 제한시간 1초.

풀이 설계

알고리즘 후보군 선택

• 정점의 수와 간선의 수를 보면 $O(N \log N)$ 이하의 알고리즘으로 풀어야 함을 알 수 있다.
• 선택 가능한 알고리즘의 후보군으로는 아래와 같은 것들이 먼저 떠올랐다.
  • Dijkstra (with priority queue): $O((V+E) \log E)$
  • DFS: $O(V+E)$
  • BFS: $O(V+E)$
  • …

그래프 탐색 접근 설계

예상 시간복잡도

• $K$를 제외한 모든 정점에 대하여, 물의 높이를 계산해가며 그래프 탐색을 수행할 때, $K$번 정점에 도달할 수 있는가를 구해야한다.
  • 이 경우 시간복잡도가 $O(V^2+VE)$로 예상된다.
    • 그래프 탐색 (DFS or BFS) : $O(V+E)$
    • 모든 정점 $V$개에 대하여 그래프 탐색 : $O(V(V+E))$
  • $(V^2+VE)$는 $10^8$을 아득히 상회한다. 따라서, 시간 초과를 피할 수 없을 것으로 예상된다.

시간 복잡도 개선

• 그래프 탐색에 대하여, 방문 상태 공유

  • 새로운 그래프 탐색을 시작할 때 마다 방문 상태를 초기화 하지 않고 사용하면 최종 시간 복잡도를 $O(V+E)$로 줄일 수 있다.
  • 단, 이 경우 물이 튀어오름으로 인해 발생하는 변수를 고려하지 못하므로 풀이한 답의 옳음은 보장할 수 없음.

• 그래프 탐색을 역방향으로 진행

  • 문제의 요구사항을 반대로 뒤집어, $K$번 정점에 도달한 물 높이 $h$가 $h \geq H_K$를 만족하게 할 수 있는 정점 $u$가 존재하는지를 찾는다.
    • 임의의 간선 $v \to u$ 에 대하여, 정점 $u$ 에서의 물 높이가 $h_u$ 이상이 되려면 정점 $v$에서의 물 높이 $h_v$는 $\frac{h_v+H_u}{2} \geq h_u$를 만족시켜야 하므로 $h_v >= 2h_u - H_u$ 가 된다.
  • 이 경우, $K$번 정점에서 그래프 탐색을 시작한다.
  • 예상되는 풀이의 최종 시간 복잡도는 $O(V+E)$이다.

풀이 구체화

전체 코드 흐름

import sys


MAX_N = 200000

# 문제의 입력 형식에 맞추어 그래프를 구성하고, 각 계곡의 높이를 입력받는다.
N, K = map(int, sys.stdin.readline().split())
H = [None, *map(int, sys.stdin.readline().split())]
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v = map(int, sys.stdin.readline().split())
    G[u].append(v)
    G[v].append(u)


def solve() -> bool:
    # TODO: K 정점에서 그래프 탐색을 수행한다.
    pass


# 문제의 정답을 출력한다.
print('1' if solve() else '0')

• u, v를 받을 때 정점 번호가 $1$부터 시작하는 것을 반영하기 위하여, H와 G 리스트의 좌측에 1칸 씩 더미 값을 padding 해주었다.

DFS로 구현하는 경우

def solve() -> bool:
    visited = [False] * (N+1)

    # 재귀 호출은 O(V+E)번 일어날 수 있으므로, 재귀 깊이 제한을 늘린다.
    sys.setrecursionlimit(MAX_N+MAX_N)

    def dfs(u: int, h: float) -> bool:
        # u에서 출발하여 K에 도달할 수 있는지 확인한다.
        # h는 K에 도달하기 위해 u에서 물의 높이가 얼마나 높아야 하는지를 나타낸다.

        if u != K and H[u] >= h:
            # K가 아닌 임의의 정점 u에 대하여,
            # u를 출발점으로 하여 K에 도달할 수 있는 경우를 발견함.
            return True

        for v in G[u]:
            if not visited[v]:
                visited[v] = True
                # v에서의 물 높이는 2*h-H[u] 이상이어야 한다.
                if dfs(v, 2*h-H[u]):
                    return True

        return False

    visited[K] = True
    return dfs(K, H[K])

제출 번호	결과	메모리	시간	언어	코드 길이
87179352	메모리 초과	- KB	- ms	Python 3	1321 B

• 시간 복잡도는 맞춰주었지만, 재귀호출 시에 파이썬 특유의 메모리 자원을 많이 요구하는 성질로 인하여 MLE를 받은 것으로 보인다.
• 아마도 다른 언어에서는 이렇게 구현하면 정상적으로 AC 맞지 않을까 싶다.

BFS로 구현하는 경우

def solve() -> bool:
    visited = [False] * (N+1)

    from collections import deque
    queue = deque()

    queue.append((K, H[K]))
    visited[K] = True
    while queue:
        u, h = queue.popleft()

        if u != K and H[u] >= h:
            # K가 아닌 임의의 정점 u에 대하여,
            # u를 출발점으로 하여 K에 도달할 수 있는 경우를 발견함.
            return True

        for v in G[u]:
            if not visited[v]:
                # v에서의 물 높이는 2*h-H[u] 이상이어야 한다.
                queue.append((v, 2*h-H[u]))
                visited[v] = True

    return False

제출 번호	결과	메모리	시간	언어	코드 길이
87179383	맞았습니다!!	72648 KB	1508 ms	Python 3	1081 B

풀이 결과

최종 시간 복잡도

• $O(V+E) = O(N)$

풀이 알고리즘/자료구조

• 수학
  • 물 높이 계산 & 역산
• 그래프 탐색
  • DFS or BFS