[백준 17265] 나의 인생에는 수학과 함께 (Java)

문제 링크: https://www.acmicpc.net/problem/17265

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

1. 주의할 점

- 이동 가능한 방법으로는 하하, 하우, 우하, 우우 총 4가지의 방법이 존재한다

 

2. 구현

- Check[][][] 배열을 통해 각 지점까지 이동할 때 얻을 수 있는 최대 및 최소값을 저장한다

- BFS() 함수를 2번 수행하여 한 번은 최대를, 다른 한번은 최소를 구하도록 한다

- BFS 탐색을 수행하기전, Check[][] 배열을 초기화하고 시작한다

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static final int dx[] = {0,1};
    static final int dy[] = {1,0};
    static int num,mini,maxi;
    static char arr[][];
    static int check[][][];
    
    static class Info{
        int y,x,val;
        
        public Info(int y, int x, int val){
            this.y=y;
            this.x=x;
            this.val=val;
        }
    }
    
    //[][][0]: 최대, [][][1]: 최소
    static void bfs(int flag){
        //초기화
        for(int i=0;i<num;i++)
            for(int j=0;j<num;j++){
                if(flag==0) check[i][j][flag] = -4000;
                else check[i][j][flag] = 4000;
            }
        Queue<Info> q = new LinkedList<>();
        int val = arr[0][0]-'0';
        q.offer(new Info(0,0,val));
        check[0][0][flag]=val;
        while(!q.isEmpty()){
            Info ii = q.poll();
            int cy = ii.y;
            int cx = ii.x;
            int cv = ii.val;
            if(check[cy][cx][flag]!=cv) continue;
            for(int i=0;i<2;i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                if(nx==num || ny==num) continue;
                for(int j=0;j<2;j++){
                    int nnx = nx+dx[j];
                    int nny = ny+dy[j];
                    if(nnx<num && nny<num){
                        int nnv = arr[nny][nnx]-'0';
                        int nv = cv;
                        if(arr[ny][nx]=='+') nv+=nnv;
                        else if(arr[ny][nx]=='-') nv-=nnv;
                        else nv*=nnv;
                        if(flag==0){
                            if(check[nny][nnx][flag]<nv){
                                check[nny][nnx][flag]=nv;
                                q.offer(new Info(nny,nnx,nv));
                            }
                        }
                        else{
                            if(check[nny][nnx][flag]>nv){
                                check[nny][nnx][flag]=nv;
                                q.offer(new Info(nny,nnx,nv));
                            }
                        }
                    }
                }
            }
        }
        System.out.print(check[num-1][num-1][flag]+" ");
    }
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    num = Integer.parseInt(br.readLine().trim());
	    //초기화
	    arr = new char[num][num];
	    check = new int[num][num][2];
	    
	    for(int i=0;i<num;i++){
	        String str = br.readLine();
	        StringTokenizer st = new StringTokenizer(str);
	        for(int j=0;j<num;j++)
	            arr[i][j] = st.nextToken().charAt(0);
	    }
	    for(int i=0;i<2;i++)
	        bfs(i);
	}
}