[백준 17265] 나의 인생에는 수학과 함께 자바 - DFS

문제

17265번: 나의 인생에는 수학과 함께

메모리

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);
    }
}