[HSAT 7회 정기 코딩 인증평가 기출] 순서대로 방문하기 자바

언어별 시간/메모리

언어시간메모리

JavaScript	1초	1024MB
C	1초	1024MB
C++	1초	1024MB
Java	1초	1024MB
Python	1초	1024MB

Sam은 팀장님으로부터 차량이 이동 가능한 시나리오의 수를 찾으라는 업무 지시를 받았습니다. 이동은 숫자 0과 1로만 이루어져 있는 n x n 크기의 격자 위에서 일어납니다. 숫자 0은 빈 칸을 의미하며, 숫자 1은 해당 칸이 벽으로 막혀 있음을 의미합니다. 아래는 n이 3인 경우의 예시입니다.

 

0 0 0
0 0 0
0 0 1

 

차량은 n x n 격자 내에서 m개의 지점을 순서대로 방문하려고 합니다. 이 때 이동은 항상 상하좌우 중 인접한 칸으로만 이동하되 벽은 지나갈 수 없으며, 한 번 지났던 지점은 다시는 방문해서는 안 됩니다. 이러한 조건 하에서 차량이 이동 가능한 서로 다른 가지 수를 구하는 프로그램을 작성해보세요.

 

방문해야 하는 지점의 첫 지점이 출발점이며, 마지막 지점이 도착점임에 유의합니다.

 

위의 예에서 m = 3, 방문해야 하는 지점이 순서대로 (3행, 1열), (1행, 2열), (2행, 3열)이라면, 다음과 같이 5가지의 시나리오가 가능합니다.

 

1. (3행, 1열) → (3행, 2열) → (2행, 2열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

 

2. (3행, 1열) → (3행, 2열) → (2행, 2열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

 

3. (3행, 1열) → (2행, 1열) → (2행, 2열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

 

4. (3행, 1열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

 

5. (3행, 1열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (2행, 2열) → (2행, 3열)

 

제약조건

[조건 1] 2 ≤ n ≤ 4

[조건 2] 2 ≤ m ≤ n2

입력형식

첫 번째 줄에는 격자의 크기를 나타내는 n과 순서대로 방문해야 하는 칸의 수 m이 공백을 사이에 두고 주어집니다.

 

두 번째 줄부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 수가 공백을 사이에 두고 주어집니다. 주어지는 수는 0 또는 1이며, 0은 빈 칸을 1은 벽을 의미합니다.

 

n + 2 번째 줄부터는 m개의 줄에 방문해야 할 m개의 칸의 위치 (x, y) 쌍이 공백을 사이에 두고 한 줄에 하나씩 순서대로 주어집니다. 주어지는 칸에 벽이 있는 경우는 없으며, 동일한 칸이 여러 번 주어지는 경우는 없다고 가정해도 좋습니다.

출력형식

차량이 m개의 지점을 순서대로 방문할 수 있는 서로 다른 방법의 수를 출력합니다. 만약 가능한 방법이 없다면 0을 출력합니다.

입력예제1

3 3 0 0 0 0 0 0 0 0 1 3 1 1 2 2 3

출력예제1

5

 

입력예제2

3 3 0 0 1 0 0 0 0 0 1 3 1 1 2 2 3

출력예제2

1

 

 

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

public class Main {

    static int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
    static int n,m;
    static int[][] map;
    static boolean[][] visited;
    static List<int[]> checkPoints = new ArrayList<>();
    static int result = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        map = new int[n][n];
        visited = new boolean[n][n];
        
        
        for (int i=0; i<n; i++) {
            input = br.readLine().split(" ");
            for (int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }

        
        for (int i=0; i<m; i++) {
            input = br.readLine().split(" ");
            int r = Integer.parseInt(input[0]) - 1;
            int c = Integer.parseInt(input[1]) - 1;
            checkPoints.add(new int[]{r,c});
        }

        visited[checkPoints.get(0)[0]][checkPoints.get(0)[1]] = true;
        dfs(checkPoints.get(0)[0],checkPoints.get(0)[1], 1);

        System.out.println(result);
    }

    static void dfs(int r, int c, int depth) {
        // 지금 도착한 장소가 체크포인트라면
        if (r == checkPoints.get(depth)[0] && c == checkPoints.get(depth)[1]) {

            // 마지막 체크포인트라면
            if (depth == m - 1) {
                result++;
                return;
            } 
            // 아니라면
            else {
                depth++;
            }
        }

        for (int i=0; i<4; i++) {
            int nr = r + dir[i][0];
            int nc = c + dir[i][1];

            // map 밖으로 나가면 안됨
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;

            // 벽으론 못감
            if (map[nr][nc] == 1) continue;

            // 이미 들린 곳은 못감
            if (visited[nr][nc] == true) continue;

            visited[nr][nc] = true;
            dfs(nr,nc,depth);
            visited[nr][nc] = false;
        }
    }
}

 

 

n이 값이 작기 때문에 해당 풀이로 풀었다. 

 

위 풀이에선 잘못된 순서로 갈 경우에 그것이 잘못된 경로라는걸 인지 못하고 끝까지 탐색한다. 

 

만약 n이 클 경우엔 문제가 생기지 않을까 ? 그래서 set에 경로를 담아서 현재 경로가 set에 contain 되어있는지 여부를 검사하고, 잘못된 순서일경우 back 하는 로직을 추가하면 좀 더 효율적이지 않을까 생각해본다.. 매번 set을 검사하는거라 결국 거기서 거긴가.. 잘 모르겠다.