Softeer 2050
https://softeer.ai/practice/info.do?idx=1&eid=2050

문제

---

생각하기

---

• DFS 백트래킹을 통해서 답을 구할 수 있다.

동작

결과

코드

---

Java

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

public class Main {
    // input
    private static BufferedReader br;

    // variables
    private static int N, M, ans;
    private static Coordinate start;
    private static int[][] map;
    private static boolean[][] isVisited;
    private static Coordinate[] visitArr;

    private static int[] dirX = {-1, 1, 0, 0};
    private static int[] dirY = {0, 0, -1, 1};

    private static class Coordinate {
        int x;
        int y;

        private Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "x : " + x + ", y : " + y;
        }
    } // End of Coordinate class

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        isVisited[start.x][start.y] = true;
        DFS(start.x, start.y, 1);

        sb.append(ans);
        return sb.toString();
    } // End of solve()

    private static void DFS(int x, int y, int depth) {
        if (depth == M) {
            ans++;
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nextX = x + dirX[i];
            int nextY = y + dirY[i];

            if (!ableCheck(nextX, nextY)) continue;

            isVisited[nextX][nextY] = true;
            int temp = 0;
            if (visitArr[depth].x == nextX && visitArr[depth].y == nextY) {
                temp = 1;
            }

            DFS(nextX, nextY, depth + temp);
            isVisited[nextX][nextY] = false;
        }
    } // End of DFS()

    private static boolean ableCheck(int nextX, int nextY) {
        return nextX >= 1 && nextX <= N && nextY >= 1 && nextY <= N && !isVisited[nextX][nextY] && map[nextX][nextY] != 1;
    } // End of ableCheck

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        ans = 0;
        map = new int[N + 1][N + 1];
        visitArr = new Coordinate[M];
        isVisited = new boolean[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            visitArr[i] = new Coordinate(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        start = visitArr[0];
    } // End of input()
} // End of Main class