이런 정석적인? 백트래킹 문제 오랜만에 풀어서 재미있었다 ㅎㅅㅎ
이런 문제만 풀고 싶어...
👀 문제
17265번: 나의 인생에는 수학과 함께 ✨ 골드 5
세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 계산하고 한걸음 한걸음 보폭을 계산하여 자신의 활동량을 확인하며 인생의 목표를 실행하며 살아가고 있다. 그런 세현이는 매일 학교를 가면서 지나가는 길에도 수학을 적용시키고 싶었다.
세현이네 집에서 학교까지 가는 길은 N x N 크기의 바둑판과 같다. 그리고 각 블록은 1x1 정사각형으로 구분 지을 수 있다. 세현이는 그 블록마다 숫자와 연산자가 존재한다고 생각해서 임의의 숫자와 연산자를 각 블록에 넣어 바둑판을 만들었다.
세현이는 학교에서 집으로 가는 경로에서 만나는 숫자와 연산자의 연산 결과의 최댓값과 최솟값을 구하려고 한다. 세현이는 항상 자신의 집 (1, 1)에서 학교 (N, N)까지 최단거리로 이동한다. 최단거리로 이동하기 위해서는 오른쪽과 아래쪽으로만 이동해야 한다.
위와 같이 N = 5 인 5 x 5 바둑판을 만들었다고 해보자.
그림 1의 경로를 통해 집(1, 1)에서 학교(N, N)까지 어떻게 연산이 되는지 확인해보자. 경로에서 만나는 연산자들의 우선순위는 고려하지 않는다.
- 5 → × → 4 = 20
- 20 → + → 5 = 25
- 25 → ×→ 5 = 125
- 125 → + → 2 = 127
그림 1은 최댓값을 가지는 경로이며 127이라는 최댓값을 얻을 수 있다.
그리고 위와 같이 연산하여 그림 2의 경로를 통해서 최솟값으로 3을 얻을 수 있다.
세현이는 이 길을 걸으면서 최댓값과 최솟값을 암산하다가 교통사고를 당해 현재 인하대학교 병원에 입원했다. 아픈 세현이를 위해 최댓값과 최솟값을 구해주자.
예제 입력
5
5 + 5 - 3
* 3 - 1 -
4 + 5 + 2
- 2 * 3 -
1 * 5 + 2예제 출력
127 3🔑 키포인트
그래프 이론 깊이 우선 탐색
✍️ 코드
📍 dfs! 함수의 파라미터에 연산자와 결과값을 담는 방식을 사용해 풀었다.
💡 최댓값이 음수일 수도 있음에 주의하고 풀어야 한다. 처음에 아무 생각 없이 max_value 초기값을 0으로 줘서 틀렸다!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ17265_나의인생에는수학과함께 {
static int n;
static boolean[][] visited;
static char[][] map;
static int[] dx = { 1, 0 };
static int[] dy = { 0, 1 };
static int max_value, min_value;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
map = new char[n][n];
visited = new boolean[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
map[i][j] = st.nextToken().charAt(0);
}
}
max_value = Integer.MIN_VALUE;
min_value = Integer.MAX_VALUE;
visited[0][0] = true;
dfs(0, 0, map[0][0] - '0', ' ');
System.out.println(max_value + " " + min_value);
}
static void dfs(int x, int y, int num, char cal) {
if (x == n - 1 && y == n - 1) {
max_value = Math.max(max_value, num);
min_value = Math.min(min_value, num);
return;
}
for (int i = 0; i < 2; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (!visited[nx][ny]) {
visited[nx][ny] = true;
if (map[nx][ny] == '+' || map[nx][ny] == '-' || map[nx][ny] == '*') {
dfs(nx, ny, num, map[nx][ny]);
} else {
int next = map[nx][ny] - '0';
if (cal == '+') {
dfs(nx, ny, num + next, ' ');
} else if (cal == '-') {
dfs(nx, ny, num - next, ' ');
} else {
dfs(nx, ny, num * next, ' ');
}
}
visited[nx][ny] = false;
}
}
}
}
}