오늘의 키워드
•
BFS
•
숫자/연산자 구분 처리
•
Character → Integer 변환
•
최댓값, 최솟값 경로 탐색
문제 파악 및 풀이
•
(0, 0)부터 시작하여 (n-1, n-1)까지 이동하며 만나는 숫자와 연산자들로 최댓값과 최솟값을 계산하는 문제이다.
•
이동 경로는 오른쪽 또는 아래 방향으로만 가능하다.
•
각 위치에는 숫자 또는 연산자가 번갈아가며 배치되어 있고, 연산자 다음에 반드시 숫자가 오기 때문에 직전에 어떤 연산자인지를 기억하며 연산을 수행해야 한다.
•
BFS를 통해 가능한 모든 경로를 탐색하며 최댓값과 최솟값을 동시에 갱신했다.
놓쳤던 부분
•
Character를 숫자로 변환하지 않고 바로 사용한 탓에, 문자의 아스키 코드값이 계산에 들어가 터무니없는 숫자 결과가 나왔다.
•
Character.getNumericValue()로 변환하는 부분을 처음에 놓쳤던 게 핵심 실수였다.
최종 풀이 코드
import java.io.*;
import java.util.*;
class Node {
int x;
int y;
int score;
char pre;
public Node(int x, int y, int score, char pre) {
this.x = x;
this.y = y;
this.score = score;
this.pre = pre;
}
}
class Main {
public static int n;
public static Character[][] matrix;
public static int min = Integer.MAX_VALUE;
public static int max = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
init();
bfs();
System.out.println(max + " " + min);
}
public static void bfs() {
Deque<Node> dq = new ArrayDeque<>();
dq.addLast(new Node(0, 0, Character.getNumericValue(matrix[0][0]), ' '));
int[][] delta = {{0, 1}, {1, 0}};
while (!dq.isEmpty()) {
Node node = dq.removeFirst();
int x = node.x;
int y = node.y;
int score = node.score;
char pre = node.pre;
if (x == n - 1 && y == n - 1) {
max = Math.max(max, score);
min = Math.min(min, score);
continue;
}
for (int[] d : delta) {
int nx = x + d[0];
int ny = y + d[1];
if (canGo(nx, ny)) {
char next = matrix[nx][ny];
if (Character.isDigit(next)) {
dq.addLast(new Node(nx, ny, calculate(score, pre, Character.getNumericValue(next)), pre));
} else {
dq.addLast(new Node(nx, ny, score, next));
}
}
}
}
}
public static int calculate(int score, char operator, int operand) {
switch (operator) {
case '+': return score + operand;
case '-': return score - operand;
case '*': return score * operand;
}
return 0;
}
public static boolean canGo(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < n;
}
public static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
matrix = new Character[n][n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
matrix[i][j] = st.nextToken().charAt(0);
}
}
}
}
Java
복사
시간 복잡도
•
O(2^(2N)) 경로 탐색
◦
모든 경로를 BFS로 탐색하므로 완전 탐색 수준의 시간 복잡도 발생
◦
단, 입력 크기가 작기 때문에 통과 가능
오늘의 회고
어려웠던 점
•
숫자라고 생각하고 사용한 값이 사실 char였고, 이로 인해 엉뚱한 값(아스키 코드)이 계산에 사용되는 오류가 생겼다.
•
BFS 탐색 구조는 익숙했지만 입력 처리 실수가 전체 흐름을 망칠 수 있다는 걸 체감했다.
개선점
•
숫자와 문자를 명확하게 구분하고, char → int 변환 시점에 항상 조심할 것
•
연산자 처리와 숫자 누적이 섞인 문제에서는 데이터 타입과 값 확인을 습관화하자.