오늘의 키워드
•
BFS
•
우선순위 큐 (PriorityQueue)
•
조건에 따른 탐색 제한
문제 파악 및 풀이
•
해당 문제를 보고 처음에는 BFS를 활용해서 풀어야겠다고 생각했다.
•
이때 Deque와 PriorityQueue 중 어떤 자료구조를 사용할지 고민했다.
•
Deque를 사용할 경우 방문 체크가 필요해 보였고, PriorityQueue를 사용하면 방문 체크 없이도 항상 최소 경로를 우선 탐색할 수 있다는 점에서 공간 및 시간 측면에서 더 효율적이라 판단했다.
핵심 조건
•
연속으로 같은 방향(왼쪽, 아래, 오른쪽)으로 이동할 수 없다.
•
시작 지점은 첫 번째 행의 아무 열이나 가능하며, 마지막 행에 도달했을 때 최소 합을 구하는 문제이다.
최종 풀이 코드
import java.io.*;
import java.util.*;
class Node implements Comparable<Node>{
int x;
int y;
int before;
int score;
public Node(int x, int y, int before, int score) {
this.x = x;
this.y = y;
this.before = before;
this.score = score;
}
@Override
public int compareTo(Node o) {
if (this.score == o.score) {
return o.x - this.x;
}
return this.score - o.score;
}
}
class Main {
public static final int MAX_N = 6;
public static final int MAX_V = 100;
public static final int MAX_NUM = Integer.MAX_VALUE;
public static int n, m;
public static int ans = MAX_NUM;
public static int[][] matrix;
public static PriorityQueue<Node> pq = new PriorityQueue<>();
public static void main(String[] args) throws IOException {
init();
for (int i = 0; i < m; i++) {
ans = Math.min(ans, start(0, i));
}
System.out.println(ans);
}
public static int start(int x, int y) {
pq.offer(new Node(x, y, MAX_NUM, matrix[0][y]));
while (!pq.isEmpty()) {
Node node = pq.poll();
x = node.x;
y = node.y;
if (x == n - 1) {
return node.score;
}
for (int i = -1; i <= 1; i++) {
if (node.before == i) continue;
int nx = x + 1;
int ny = y + i;
if (canGo(nx, ny)) {
pq.offer(new Node(nx, ny, i, node.score + matrix[nx][ny]));
}
}
}
return MAX_NUM;
}
public static boolean canGo(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
}
public static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
matrix = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken());
}
}
}
}
Java
복사
시간 복잡도
•
O(N × M × 3)
◦
각 칸에서 3방향(왼쪽 대각, 아래, 오른쪽 대각)으로 이동을 고려하고,
◦
PriorityQueue로 탐색 순서를 조절하면서도 모든 칸을 방문할 수 있다.
◦
최악의 경우 모든 칸과 방향을 탐색하므로 O(NM3)
오늘의 회고
어려웠던 점
•
Deque와 PriorityQueue 중 어떤 자료구조를 사용할지 고민이 있었다.
•
방문 체크가 필요한지에 대한 판단이 어려웠다.
개선점
•
우선순위 큐를 사용하면 방문체크 없이 최솟값 경로를 빠르게 찾을 수 있다는 점을 다시 한 번 실감했다.
•
BFS/DFS 응용 문제에서 탐색 조건과 방문 기준을 명확히 세우는 연습이 필요하다.
•
그리디, DP 외에도 탐색 최적화 전략(PQ, DP+DFS 등) 에 대한 감각을 꾸준히 쌓아야겠다.