[Softeer HSAT 7회] 순서대로 방문하기 - Java[자바]

링크

문제

문제

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열)

풀이

• 한 번 지났던 지점은 다시는 방문해서는 안 됩니다.
  - 이 문장을 통해서 visit 배열을 만들어야 하는 것을 고려합니다.
• n이 매우 작으므로 완전탐색(dfs)를 고려합니다.
  - 다만 중간 도착지가 있으므로 이를 고려하여 작성합니다.

import java.io.*;  
import java.util.*;  
  
public class Main {  
  
    // 격자의 크기를 나타내는 n    static int n;  
    // 순서대로 방문해야 하는 칸의 수  
    static int m;  
    // 차량이 m개의 지점을 순서대로 방문할 수 있는 서로 다른 방법의 수  
    static int count = 0;  
    // 2차원 배열을 이동하기 위한 deltaX, deltaY배열  
    static final int[] dx = {0, 1, 0, -1};  
    static final int[] dy = {1, 0, -1, 0};  
    static int[][] grid;  
    static boolean[][] visited;  
    // 차량이 방문해야 하는 지점들의 좌표를 저장하는 배열(리스트를 사용해도 됨)  
    static Point[] destinations;  
  
    public static void main(String[] args) throws IOException {  
        // 입력과 초기화  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        n = Integer.parseInt(st.nextToken());  
        m = Integer.parseInt(st.nextToken());  
        grid = new int[n][n];  
        visited = new boolean[n][n];  
        destinations = new Point[m];  
  
        for (int i = 0; i < n; i++) {  
            // 잘 외워두시면 좋습니다.  
            grid[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();  
        }  
  
        for (int i = 0; i < m; i++) {  
            st = new StringTokenizer(br.readLine());  
            destinations[i] = new Point(Integer.parseInt(st.nextToken()) - 1,  
                Integer.parseInt(st.nextToken()) - 1);  
        }  
  
        // dfs를 이용하여 모든 경우의 수를 탐색합니다.  
        // 시작점과 방문한 지점의 수를 인자로 넘겨줍니다.  
        dfs(destinations[0], 1);  
  
        System.out.println(count);  
    }  
  
    /**  
     * @param cur  현재 위치  
     * @param index 현재까지 방문한 지점의 수  
     */  
    private static void dfs(Point cur, int index) {  
        if (cur.equals(destinations[index])) {  
            // 마지막 지점에 도착하면 count를 증가시키고 종료합니다.  
            if (index == m - 1) {  
                count++;  
                return;  
            }  
            index++;  
        }  
        int curX = cur.x;  
        int curY = cur.y;  
        // 현재 위치를 방문했다고 표시합니다.  
        visited[curX][curY] = true;  
        // 현재 위치에서 4방향으로 이동합니다.  
        for (int i = 0; i < 4; i++) {  
            int nextX = curX + dx[i];  
            int nextY = curY + dy[i];  
  
            // 격자를 벗어나면 continue합니다.  
            if (outOfRange(nextX, nextY)) {  
                continue;  
            }  
            // 이미 방문한 지점이면 continue합니다.  
            if (visited[nextX][nextY]) {  
                continue;  
            }  
            // 벽이면 continue합니다.  
            if (grid[nextX][nextY] == 1) {  
                continue;  
            }  
            // 다음 지점으로 이동합니다.  
            dfs(new Point(nextX, nextY), index);  
        }  
        // 방문 기록을 초기화합니다.  
        visited[curX][curY] = false;  
    }  
  
    /**  
     * @param nextX 다음 위치의 x좌표  
     * @param nextY 다음 위치의 y좌표  
     * @return 격자를 벗어나면 true, 아니면 false  
     */    private static boolean outOfRange(int nextX, int nextY) {  
        return nextX < 0 || nextX >= n || nextY < 0 || nextY >= n;  
    }  
  
    /**  
     * 좌표를 나타내는 클래스  
     * x, y좌표를 가집니다.  
     * equals()를 오버라이드하여 좌표가 같으면 같은 객체로 인식하도록 합니다.  
     */    static class Point {  
  
        int x;  
        int y;  
  
        private Point() {  
        }  
  
        public Point(int x, int y) {  
            this.x = x;  
            this.y = y;  
        }  
  
        @Override  
        public boolean equals(Object o) {  
            if (this == o) {  
                return true;  
            }  
            if (o == null || getClass() != o.getClass()) {  
                return false;  
            }  
            Point point = (Point) o;  
            return x == point.x && y == point.y;  
        }  
    }  
}

기초적인 백트래킹 문제입니다.

코드에 주석을 통하여 각각의 코드에 대한 설명을 적어두었습니다.