728x90
반응형
문제
메모리 | 11532KB | 시간 | 80MS |
접근방식
DFS로 내려가면서 현재가 연산자인 경우 다음의 값을 연산하는 식으로 진행했다. 완전탐색이고 결과값이 음수가 나올 수 있어서 max값을 0이 아닌 Integer.MAX_INTEGER로 초기화하는 게 중요했다.
public static void DFS(int x,int y,int sum) {
if(x == N-1 && y == N-1) {
min = Math.min(min, sum);
max = Math.max(max, sum);
return;
}
visited[x][y] = true;
for (int i = 0; i < dx.length; i++) {
int nx = x+dx[i];
int ny = y+dy[i];
if(nx >= 0 && nx < N && ny >=0 && ny < N) {
if(!visited[nx][ny]) {
if(board[x][y] == '+') {
DFS(nx,ny,sum + (board[nx][ny]-'0'));
}else if(board[x][y] == '-') {
DFS(nx,ny,sum - (board[nx][ny]-'0'));
}else if(board[x][y] == '*') {
DFS(nx,ny,sum * (board[nx][ny]-'0'));
}else {
DFS(nx,ny,sum);
}
}
}
}
visited[x][y] = false;
}
풀이
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Solution {
static int N,min= Integer.MAX_VALUE,max=Integer.MIN_VALUE;
static char board[][];
static boolean visited[][];
static int[] dx = {1,0};
static int[] dy = {0,1};
public static void DFS(int x,int y,int sum) {
if(x == N-1 && y == N-1) {
min = Math.min(min, sum);
max = Math.max(max, sum);
return;
}
visited[x][y] = true;
for (int i = 0; i < dx.length; i++) {
int nx = x+dx[i];
int ny = y+dy[i];
if(nx >= 0 && nx < N && ny >=0 && ny < N) {
if(!visited[nx][ny]) {
if(board[x][y] == '+') {
DFS(nx,ny,sum + (board[nx][ny]-'0'));
}else if(board[x][y] == '-') {
DFS(nx,ny,sum - (board[nx][ny]-'0'));
}else if(board[x][y] == '*') {
DFS(nx,ny,sum * (board[nx][ny]-'0'));
}else {
DFS(nx,ny,sum);
}
}
}
}
visited[x][y] = false;
}
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());
board = new char[N][N];
visited = new boolean[N][N];
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < N; j++) {
board[i][j] = input.charAt(j*2);
}
}
DFS(0,0,board[0][0]-'0');
System.out.println(max+" "+min);
}
}
728x90
'코딩테스트' 카테고리의 다른 글
[백준 17281] 야구 자바 - 완전탐색 (0) | 2023.10.13 |
---|---|
[백준 14719] 빗물 자바 구현 (0) | 2023.10.12 |
[백준 2864] 5와 6의 차이 자바 문자열 (0) | 2023.06.15 |
[백준 2935] 소음 자바 문자열 (0) | 2023.06.15 |
[백준] 2023 신기한 소수 자바 (0) | 2023.05.30 |