Softeer - 순서대로 방문하기 - Java

1. 문제

https://softeer.ai/practice/6246

2. 풀이

https://www.youtube.com/watch?v=r0plARDF5dE&t=805s

처음에는 BFS풀이를 생각했다가 풀이를 보고 DFS가 나을것이라고 판단하여 DFS로 풀이했다.

2-1. ✨핵심 Point

완전탐색을 통하여 destIndex == M - 1(마지막 방문점) 이라면 count를 증가시키고 그냥 return해주면 된다.

visit[x][y] = true를 for문 전에 해주고, for문 후에 다시 false로 바꿔야 완전탐색이 가능하다.

3. 코드

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

public class Main {

    static int N;
    static int M;
    static int map[][];
    static boolean visit[][];
    static int destX[];
    static int destY[];
    static int moveX[] = {1, -1, 0, 0};
    static int moveY[] = {0, 0, 1, -1};
    static int count;
    
    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];
        visit = new boolean[N][N];
        destX = new int[M];
        destY = new int[M];
        count = 0;
        
        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 m = 0; m < M; m++){
            st = new StringTokenizer(br.readLine(), " ");

            destX[m] = Integer.parseInt(st.nextToken()) - 1;
            destY[m] = Integer.parseInt(st.nextToken()) - 1;
        }

        dfs(destX[0], destY[0], 0);
        System.out.println(count);
    }

    public static void dfs(int x, int y, int destIndex){
        if(x == destX[destIndex] && y == destY[destIndex]){
            if(destIndex == M - 1){
                count += 1;
                return;
            } else {
                destIndex += 1;
            }
        }

        visit[x][y] = true;
        for(int i = 0; i < moveX.length; i++){
            int goX = x + moveX[i];
            int goY = y + moveY[i];

            if(goX < 0 || goY < 0 || goX >= N || goY >= N)
                continue;

            if(map[goX][goY] == 1 || visit[goX][goY])
                continue;

            dfs(goX, goY, destIndex);
        }
        visit[x][y] = false;
    }
}