구름 - 길찾기 (다이아몬드)

https://level.goorm.io/exam/43145/%EA%B8%B8%EC%B0%BE%EA%B8%B0-%EB%8B%A4%EC%9D%B4%EC%95%84%EB%AA%AC%EB%93%9C/quiz/1

구름LEVEL

• 그래프 탐색 문제이다.
• 입력 형식이 다소 난해 했다.
• DFS로 완전 탐색하였다.
• 다이아몬드의 마지막 지점에서 경로를 출력했으며 전역변수로 갱신했다.
• 다른 사람 풀이 보면 DFS 함수에서 바로 경로 리턴하는 방식이 있었다. 코드가 깔끔한거 같기도.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {
    public static int maximumPath = -1;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[][] map = new int[1001][1001];

        for (int i = 1; i <= (N - 1) * 2 + 1; i++) {
            String[] s = br.readLine().split(" ");
            for (int j = 0; j < s.length; j++) {
                map[i][j + 1] = Integer.parseInt(s[j]);
            }
        }

        dfs(1, 1, map, N, 1, 0);
        System.out.println(maximumPath);
    }

    private static void dfs(int r, int c, int[][] map, int N, int depth, int sum) {
        if (r > map.length) return;
        if (c > map[r].length) return;

        Integer node = map[r][c];
        sum += node;

        if (r == (N - 1) * 2 + 1 && c == 1) {
            maximumPath = Math.max(maximumPath, sum);
            return;
        }

        if (depth < N) {
            if (map[r + 1][c] != 0) {
                dfs(r + 1, c, map, N, depth + 1, sum);
            }

            if (map[r + 1][c + 1] != 0) {
                dfs(r + 1, c + 1, map, N, depth + 1, sum);
            }
        } else {
            if (map[r + 1][c] != 0) {
                dfs(r + 1, c, map, N, depth + 1, sum);
            }

            if (map[r + 1][c - 1] != 0) {
                dfs(r + 1, c - 1, map, N, depth + 1, sum);
            }
        }

    }
}