JY.think()

1. 최대 K번 안에 도달

"경유 k번 이내"처럼 횟수 제한이 붙는 유형. 1차원 dist로는 안 된다.

         100           100
  (0) ────────→ (1) ────────→ (2)
   │                           ↑
   └───────────────────────────┘
                500

k = 0(직항)이면 답은 500인데, 평범하게 돌리면 더 싼 200이 500을 밀어낸다.

그리고 그 200은 나중에 횟수 제한에 걸려 죽는다.

이 문제는 싼 경로가 이기는 게 아니다. 비교하면 안 되는 두 경로를 dist[2] 한 칸에 넣은게 원인이다.

그래서 칸을 나눈다. 정점을 노드 하나가 아니라 (노드, 사용한 간선 수) 쌍으로 본다.

dist[i][j] = i번 노드까지 간선을 정확히 j개 써서 가는 최소 비용

도화선으로 치면 한 지점에 화약이 하나가 아니라 층마다 하나씩 있는 것이다.

"2번 지점 1층의 화약", "2번 지점 2층의 화약"이 각각 따로 터진다. 1층이 터졌다고 2층이 터지지는 않는다. 남남이니까.

층 번호는 곧 사용한 간선 수다. 그러니 도화선을 하나 탈 때마다 반드시 다음 층으로 넘어간다.

2층에서 출발한 불은 이웃 지점의 3층에 닿는다.

도착점을 꺼내면 바로 반환한다

dist 배열을 끝까지 채울 필요가 없다. 꺼낸 노드가 목적지면 그 자리에서 cost를 반환하면 된다.

const [node, cost, count] = pq.pop();

if (node === dst) return cost; // ← 이게 먼저

if (cost > dist[node][count]) continue;

if (count > k) continue;

힙은 비용이 가장 작은 것부터 꺼내기 때문이다.

목적지가 처음 나왔다는 건 지금 남아있는 어떤 후보보다도 싸다는 뜻이고, 앞으로 새로 생길 항목은 전부 지금 이후에 꺼낼 것들에서 파생되니 더 싸질 수 없다.

도화선으로 치면 목적지에 처음 닿은 불이 곧 가장 이른 불이다.

count를 볼 필요도 없다. 비용 기준으로 꺼냈으니 층과 무관하게 그게 최소다.

반칙으로 도달한 경우는 없나

없다. 힙에 애초에 안 들어간다.

if (count > k) continue가 push 자체를 막기 때문이다.

count가 k 이하일 때만 다음 간선을 타므로, 힙에 push되는 노드의 층은 아무리 커야 k+1이다.

그리고 k+1은 허용된 최댓값이다.

그러니 if (node === dst) return cost에 도달한 항목은 이미 규칙을 지킨 것들뿐이다.

반환하기 전에 층을 검사할 이유가 없다.

순서에 주의

dst 체크는 count > k로 걸러내는 줄보다 위에 있어야 한다.

간선을 k+1개 꽉 채워 쓰고 도착한 경우가 아래에 두면 count > k에 걸려 버려지기 때문이다.

합법적으로 도착한 답인데 검사 순서 때문에 놓치게 된다.

2. 출발지가 여러 개

1162. As Far from Land as Possible

"어느 출발지에서든 가장 가까운 거리"를 묻는 유형.

for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    const cur = grid[i][j];

    if (cur === 1) {
      pq.push([i, j, 0]);
      dist[i][j] = 0;
    }
  }
}

바뀐 건 초기화뿐이다.

도화선으로 치면 t=0에 여러 곳에 동시에 불을 붙이는 것이다. 불꽃들이 각자 번지다 중간에서 만나고, 어떤 지점에 먼저 닿은 불이 그 지점을 터뜨린다. 그 시각이 곧 "가장 가까운 출발지로부터의 거리"다.

불 입장에서는 자기가 어디서 출발했는지 알 바 아니다. 먼저 닿은 놈이 이긴다는 규칙 하나만 돌아가면 되고, 그건 출발지가 몇 개든 그대로다.

최댓값은 마지막 pop이다

이 문제는 최단 거리들 중 가장 큰 것을 답한다. 두 단계가 섞여 헷갈리기 쉬운데, 힙은 여전히 최소 힙이다.

1단계: 각 칸까지의 최단 거리   ← 최소. 힙이 하는 일
2단계: 그중 가장 큰 값         ← 최대. 답으로 고르는 일

2단계를 위해 격자를 다시 훑을 필요는 없다. pop은 거리가 커지는 순서로만 나오기 때문이다.

지금 distance를 꺼냈다면, 힙에 남은 건 전부 distance 이상이다.
새로 들어올 것도 distance + weight라 distance 이상이다.
그러니 distance보다 작은 값은 앞으로 나올 수 없다.

let answer = 0;

while (pq.size() > 0) {
  const [x, y, distance] = pq.pop();
  if (distance > dist[x][y]) continue;

  answer = distance; // 뒤엣것이 항상 크거나 같으니 덮어쓰면 된다
  ...
}

가중치가 1이라 BFS로도 풀리긴 하는데, 다익스트라로 풀어봄.

3. 비용이 합이 아닐 때

1631. Path With Minimum Effort

지금까지 dist는 늘 누적 합이었다. 이 문제는 아니다.

경로마다 그 경로의 최대 높이 차이가 하나씩 정해진다. 그 값이 가장 작은 경로를 찾는 문제다.

efforts[i][j] = (i,j)까지 가는 모든 경로 중, 경로의 최대 차이가 가장 작은 값

const diff = Math.abs(heights[nx][ny] - heights[x][y]);
const nextEffort = Math.max(effort, diff);
if (nextEffort < efforts[nx][ny]) { ... }

diff — 이번에 넘을 계단 하나.

Math.max(effort, diff) — effort는 여기까지 오며 넘은 최대다. 이번 계단과 비교해 큰 쪽이 다음 칸까지 갔을 때의 최대가 된다.

nextEffort < efforts[nx][ny] — 그렇게 만든 후보가 기존 최선보다 나은지 본다.

앞의 둘이 경로 안에서 max를, 마지막 하나가 경로들 사이에서 min을 담당한다.

비슷한 유형으로 778. Swim in Rising Water가 있다. Hard로 분류돼 있지만 1631보다 쉽다.

4. 경로 복원

나중에 추가