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

https://www.acmicpc.net/problem/17265

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

---

 

보통의 dfs문제는 방문한 위치를 다시 방문하지 않기 위해  boolean 2차원 배열을 사용해서 방문기록을 남겼다.

하지만 이번 문제는 오른쪽과 아래로만 이동하기 때문에 따로 방문기록을 남기지 않아도 된다!! (재밌는 문제였다)

 

[풀이 방법] 

1. 우선 이때까지 지나온 길의 값들을 모두 저장할  ArrayList구조를 갖는 클래스 변수 exp 선언

2. exp에 현재 위치(집)의 값을 추가하고 출발

3. 아래, 오른쪽 뱡향으로 이동 시도

    -> 만약 이동하려는 위치가 범위를 벗어나면 다음방향으로 이동 시도 

    -> 범위를 벗어나지 않는다면 exp의 맨 마지막에 다음위치의 값을 추가

4. 학교에 도착했다면 이때까지 걸어온 길의 수식을 계산한 뒤, 최솟값 최대값과 비교하여 갱신

    (수식을 계산하는 메서드는 dfs에서 빼서 따로 구현)

 

[구현코드_Java]

import java.util.Scanner;
import java.util.ArrayList;
public class Main {
	
	static int N;
	static int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
	static String[][] road;
	static int[] dx = {1, 0};
	static int[] dy = {0, 1};
	static ArrayList<String> exp = new ArrayList<>();
	
	public static void main(String[] args) {
		
		//입력받은 값 각 변수에 저장 
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		road = new String[N][N];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				road[i][j] = sc.next();
			}
		}
		exp.add(road[0][0]);
		dfs(0, 0);
		
		System.out.print(max);
		System.out.print(" ");
		System.out.println(min);
		
	}
	
	public static void dfs(int x, int y) {
		
		if((x == N - 1) && (y == N - 1)) { //학교에 도착하면 탐색 종료 
			int result = getResult();
			min = Math.min(result, min);
			max = Math.max(result, max);
			
			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) continue;
			
			exp.add(road[nx][ny]);
			dfs(nx, ny);
			exp.remove(exp.size() - 1);
			
		}
		
	}
	
	public static int getResult() { //이때까지 지나온 길의 수식을 계산 
		int result = cal(exp.get(0), exp.get(1), exp.get(2));
		for(int i = 3; i < exp.size(); i += 2) {
			result = cal(Integer.toString(result), exp.get(i), exp.get(i + 1));
		}
		return result;
	}
	
	public static int cal(String n1, String op, String n2) { //연신기호에 따라 계산 
		if("+".equals(op)) 		return Integer.parseInt(n1) + Integer.parseInt(n2);
		else if("-".equals(op)) return Integer.parseInt(n1) - Integer.parseInt(n2);
		else 					return Integer.parseInt(n1) * Integer.parseInt(n2);
	}

}