BOJ_S2_10164

📁 [S2_10164] 격자상의 경로

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ_S2_10164 {
    static int N, M, O;
    static int ox, oy;
    // 이동
    static int[] dx = {1, 0};
    static int[] dy = {0, 1};

    static int[][] map;
    static int cnt;

    static ArrayList<Integer> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // input
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        O = Integer.parseInt(st.nextToken());

        // map
        map = new int[N][M];

        // map에 수 넣어주기
        int num = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = num;
                // 동그라미 좌표 저장
                if (O != 1 && num == O) {
                    ox = j;
                    oy = i;
                }
                num++;
            }
        }

        list = new ArrayList<>();
        
        // 전체 횟수 카운팅
        cnt = 0;

        // 만약 O가 0이면 모든 경우의수 구해주면 된다
        if (O == 0) {
          // 항상 포함하는 수 ( 도착지 )
            O = M * N;
        }
        // dfs 실행
        dfs(0, 0);

        System.out.println(cnt);
    }

    public static void dfs(int x, int y) {
        // 기저조건 ( 마지막 값에 도착 )
        if (x == M - 1 && y == N - 1) {
            // 만약 리스트에 O가 있을 경우 카운팅
            if (list.contains(O)) {
                cnt++;
            }
            return;
        }

        // 이동
        for (int i = 0; i < 2; i++) {
            int nx, ny;
            nx = dx[i] + x;
            ny = dy[i] + y;

            // 먼저 범위를 넘으면 통과
            if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;

            // 만약 동그라미 좌표보다 앞이거나 밑에 있으면 통과 -> 갈 필요가 없다
            if ((nx < ox && ny > oy) || (nx > ox && ny < oy)) continue;

            // 리스트에 값 넣기
            list.add(map[ny][nx]);

            // dfs 실행
            dfs(nx, ny);

            // 백트래킹 ( 맨 뒤에 것 빼주기 )
            list.remove(list.size() - 1);
        }
    }
}

🤔 나의 생각

서브태스크가 있는 문제라 생각이 좀 필요했던 것 같다.
계획은 DFS를 활용하여 완전 탐색을 해주고 완전탐색을 하면서 좌표값들을 List에 담아서 마지막 좌표에 도착했을 때 List에 동그라미 좌표값이 있는지 확인해서 있으면 카운팅을 해준다.
이 문제의 포인트는 동그라미 좌표보다 앞이거나 밑에 있으면 통과 분기 처리해주는 것이 중요하다. ( 시간 때문에 ) -> 97번 줄
나는 처음부터 이게 문제일 것 같아 고려해서 문제를 풀어주었다.

1. 먼저 값을 입력받아 map을 완성시키고 안에 숫자를 순서대로 넣어준다.
2. 그리고 동그라미가 있는 좌표를 따로 저장한다.
3. 처음 (0,0) 부터 시작해서 (N-1,M-1)에 도착할 때 까지 dfs를 실행한다.
4. 다음 좌표로 가기 전에 범위를 벗어나거나 , 동그라미보다 (y값이 작고 x값은 큰 경우), (y값이 크고 x값은 작은 경우) 인 경우에는 갈 필요가 없기 때문에 continue를 통해 통과한다.
5. 조건을 통과한 좌표값은 list에 담아준다. 그리고 다시 dfs 호출 ( 좌표 이동 )
6. 마지막 목표 좌표에 도착하면 list를 확인해서 동그라미 값이 있으면 카운팅을 해준다.
7. 모든 좌표를 탐색한다.
8. 총 카운팅한 값을 출력해준다.