[DFS] 백준 - 17265번: 나의 인생에는 수학과 함께 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

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

 

 

문제는 잘 설명되어 있지만 여기에서 주의해야 할 게 오른쪽과 아래로만 내려갈 수 있다!

처음에 동서남북으로 다 움직이면서 답이 왜 안 나오지 그러면서 헤매었다..

 

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    static char[][] map;
    static boolean[][] visit;
    static int n;
    static int dx[] = {1, 0};
    static int dy[] = {0, 1};
    static ArrayList<Integer> nums;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        sc.nextLine();
        map = new char[n][n];
        visit = new boolean[n][n];
        nums = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String str = sc.nextLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = str.charAt(j * 2);
            }
        }

        dfs(0, 0, map[0][0] - '0');

        System.out.println(Collections.max(nums) + " " + Collections.min(nums));
    }

    private static void dfs(int x, int y, int v) {
        if (x == n - 1 && y == n - 1) {
            nums.add(v);
            return;
        }

        visit[x][y] = true;

        for (int i = 0; i < 2; i++) {
            int nowX = x + dx[i];
            int nowY = y + dy[i];

            if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < n) {
                if (!visit[nowX][nowY])
                    if (map[x][y] == '+') {
                        dfs(nowX, nowY, v + (map[nowX][nowY] - '0'));
                    } else if (map[x][y] == '-') {
                        dfs(nowX, nowY, v - (map[nowX][nowY] - '0'));
                    } else if (map[x][y] == '*') {
                        dfs(nowX, nowY, v * (map[nowX][nowY] - '0'));
                    } else
                        dfs(nowX, nowY, v);
            }
        }

        visit[x][y] = false;
    }
}