오늘의 키워드
•
DP
•
BFS (비효율적 접근)
•
최단 거리
•
점프 제약 조건 + 차단 구간
문제 파악 및 풀이
•
처음에는 최단 거리 문제처럼 보여 BFS로 접근했지만, 탐색 공간이 커서 시간 초과가 발생했다.
•
이후 DP로 점화식을 구성해 선형적으로 탐색하는 방식으로 변경하여 해결했다.
•
핵심은 특정 구간이 막혀 있고, 이동이 가능한 단위가 a 또는 b라는 점을 활용해 dp[i]를 i에 도달하기 위한 최소 횟수로 정의하는 것이다.
BFS 접근 (시간 초과 발생)
class Node {
int dog;
int cnt;
public Node(int dog, int cnt) {
this.dog = dog;
this.cnt = cnt;
}
}
// ... 생략된 init() 함수 동일 ...
public static void bfs() {
Arrays.fill(memo, Integer.MAX_VALUE);
memo[0] = 0;
dq.add(new Node(0, 0));
while (!dq.isEmpty()) {
Node node = dq.removeFirst();
int dog = node.dog;
int cnt = node.cnt;
if (memo[dog] < cnt) continue;
if (dog + a <= n && !closed[dog + a]) {
dq.addLast(new Node(dog + a, cnt + 1));
memo[dog + a] = cnt + 1;
}
if (dog + b <= n && !closed[dog + b]) {
dq.addLast(new Node(dog + b, cnt + 1));
memo[dog + b] = cnt + 1;
}
}
}
Java
복사
•
간단한 최단 경로 문제처럼 보이지만, bfs 탐색 도중 동일 노드가 여러 번 큐에 들어가면서 비효율적이었다.
DP 접근 (정답)
for (int i = 0; i <= n; i++) {
if (closed[i] || memo[i] == Integer.MAX_VALUE) continue;
if (i + a <= n && !closed[i + a]) {
memo[i + a] = Math.min(memo[i + a], memo[i] + 1);
}
if (i + b <= n && !closed[i + b]) {
memo[i + b] = Math.min(memo[i + b], memo[i] + 1);
}
}
Java
복사
•
memo[i]: i번 칸에 도달하기 위한 최소 이동 횟수
•
closed[i]: 막혀 있는 구간은 스킵
시간 복잡도
•
O(N)
◦
각 칸마다 한 번만 확인되며, a 또는 b 만큼 이동하므로 선형 시간에 해결 가능
오늘의 회고
어려웠던 점
•
BFS 접근이 익숙해서 처음에는 그 방식으로 풀려고 했지만 탐색 중복이 많아 시간 초과가 발생했다.
•
구간 차단 조건을 처리하면서 BFS의 비효율성을 느꼈다.
개선점
•
최단 거리 문제라도 조건이 단순하고, 이동 방식이 고정된 경우에는 DP로도 충분히 해결할 수 있다.
•
BFS와 DP 중 어떤 방식이 더 효율적일지, 탐색 공간 크기와 중복 탐색 가능성에 따라 판단하는 연습이 필요하다.