[Softeer] 7회 기출 순서대로 방문하기 Java

풀이

문제를 제대로 안읽어서 순서대로 방문하기 문제인데, 순서대로 방문하지 않고 풀어서 틀렸습니다.. 

처음 생각했을 때는 n=4이므로 전체 가능한 칸의 수는 16이 되고, DFS로 백트래킹 할 경우, 맥시멈 4 * 3^15 재귀 호출되고, 각 재귀 호출에서 4방향 탐색을 위해 for문을 도니까 4 * 3^15 * 4 ~= 2.3억이 나와서 시간 안에 부족하지 않나 생각했습니다. 

n이 작아서 예시를 들어서 해보니, 대부분 각 칸에서 다음으로 진행 가능한 경우가 3가지가 되지 않고 pruning 되어서 통과 될 것이라 판단하였습니다.

 

또 BFS로 풀이한다면, 풀이가 조금 더 복잡해질 것이라고 판단했습니다. 현재까지 이동한 경로에 따라, 다음 이동 할 수 있는 칸이 달라지기 때문입니다.

 

위 부분을 유의하여 순서대로 방문하는 코드를 작성하면 다음과 같습니다.

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

public class Main {

    public static class Pair {
        int y, x;

        public Pair(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    static int n, m;
    static int[][] board;
    static Pair[] spot;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    static int spotIdx;
    static int ans;
    public static void main(String[] args) throws IOException 
    {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        board = new int[n+1][n+1];
        spot = new Pair[m];
        for(int i=1; i<=n; i++) {
            s = br.readLine().split(" ");
            for(int j=1; j<=n; j++) {
                board[i][j] = Integer.parseInt(s[j-1]);
            }
        }

        for(int i=0; i<m; i++) {
            s = br.readLine().split(" ");
            int y = Integer.parseInt(s[0]);
            int x = Integer.parseInt(s[1]);
            spot[i] = new Pair(y, x);
        }

        boolean[][] vis = new boolean[n+1][n+1];
        vis[spot[0].y][spot[0].x] = true;
        dfs(spot[0].y, spot[0].x, 1, vis);
        System.out.println(ans);
    }

    public static void dfs(int y, int x, int spotIdx, boolean[][] vis) {

        // System.out.println(y + " " + x + " " + ans);
        
        if(spotIdx == m) {
            ans++;
            return;
        }

        for(int dir=0; dir<4; dir++) {
            int ny = y + dy[dir];
            int nx = x + dx[dir];
            if(ny < 1 || ny > n || nx < 1 || nx > n) continue;
            if(board[ny][nx] == 1 || vis[ny][nx]) continue;

            vis[ny][nx] = true;
            if(ny == spot[spotIdx].y &&  nx == spot[spotIdx].x) {
                dfs(ny, nx, spotIdx+1, vis);   
            } else {
                dfs(ny, nx, spotIdx, vis);
            }
            vis[ny][nx] = false;
        }
    }
}

풀이 설명

1. Spot에 입력으로 들어온 m개의 지점을 순서대로 넣습니다.

2. 현재 방문한 지점에서 다음 지점까지 경로를 탐색합니다. (1번 지점 -> 2번 지점, 2번 지점 -> 3번 지점 ...)

3. 다음 지점에 도달할 시 spotIdx를 +1 하여 재귀 호출합니다. (SpotIdx는 현재 도착해야 할 지점의 인덱스입니다.) => dfs(ny, nx, spotIdx+1, vis)

4. 이동한 칸이 지점이 아닌 경우, spotIdx를 증가시키지 않고 탐색을 진행합니다. => dfs(ny, nx, spotIdx, vis)

4. 만약 spotIdx가 m이 되면(마지막 지점까지 방문했으면) 경로의 수를 1증가 시킵니다.

5. backtracking을 방문 표시를 지우고 다음 경로를 계속 탐색합니다.