Softeer 6246번
https://softeer.ai/practice/6246/history?questionType=ALGORITHM

문제

---

생각하기

---

• 백트래킹을 통한 완전탐색 문제이다.

• 그다지 어렵지 않음

동작

결과

코드

---

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

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

    // variables
    private static int N, M, ans;
    private static int[][] map;
    private static boolean[][] isVisited;
    private static Coordinate[] visitList;
    private static final int[] dirX = {0, 0, -1, 1};
    private static final int[] dirY = {-1, 1, 0, 0};
    
    public static class Coordinate {
        int x;
        int y;

        public Coordinate(int x, int y) {
            this.x = x;
            this.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[visitList[0].x][visitList[0].y] = true;
        DFS(visitList[0].x, visitList[0].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 = dirX[i] + x;
            int nextY = dirY[i] + y;

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

            isVisited[nextX][nextY] = true;
            if(nextX == visitList[depth].x && nextY == visitList[depth].y) {
                DFS(nextX, nextY, depth + 1);   
            } else {
                DFS(nextX, nextY, depth);   
            }
             isVisited[nextX][nextY] = false;
        }
        
    } // End of DFS()

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

    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];
        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());
            }
        }

        visitList = new Coordinate[M];
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            visitList[i] = new Coordinate(a, b);
        }
    } // End of input()
} // End of Main class