문제 링크

풀이

조건이 약간 더해진 백트래킹 문제이다.
꼭 들려야하는 중간 지점들을 순서대로 방문해야한다.
방문한 노드가 들려야하는 중간 지점에 해당하면 그 노드부터 dfs를 다시 돌린다. 이 때, 이미 방문한 중간 지점이 아닌 다음 중간지점을 방문해야하므로 중간지점 인덱스를 1 만큼 증가시킨다.
마지막 중간지점까지 방문했다면, result를 1 증가시키고 return하여 다시 길을 찾는다.

코드

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

public class Main {
    static int n, m;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static int result = 0;
    static List<Point> points;
    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());

        map = new int[n][n];
        visited = new boolean[n][n];
        points = new ArrayList<>();
        
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            points.add(new Point(x, y));
        }
        Point start = points.get(0);
        visited[start.x][start.y] = true;
        dfs(start.x, start.y, 0);
        System.out.println(result);
    }

    public static void dfs(int x, int y, int pointIdx){
        if(pointIdx == m){
            result+=1;
            return;
        }
        if(x == points.get(pointIdx).x && y == points.get(pointIdx).y){
            dfs(x, y, pointIdx + 1);
            return;
        }
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny] && map[nx][ny] != 1){
                visited[nx][ny] = true;
                dfs(nx, ny, pointIdx);
                visited[nx][ny] = false;
            }
        }
    }

    public static class Point{
        int x;
        int y;

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