[Sofreer 문제풀이] Lv.3(순서대로 방문하기) feat. Java

 

DFS로 구현하는 건 어렵지 않았는데

 

문제 조건에서 방문해야 하는 특정 지점을 순서대로 방문해야한다는 부분 구현이 빠져있어서 시간이 좀 걸렸다.

 

if(x == startend[index][0] && y == startend[index][1]){// 모두 다 거치고, 마지막에 도달했다면
            if(index == m-1){
                cnt++;
                return;
            }
            index++;
        }

 

이 부분에서 index는 방문해야하는 지점을 담은 startend를 도는 인덱스이고,

index == m-1, 즉 마지막까지 방문했을 때 return하는 식으로 구현해야 한다.

 

 

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

public class Main {

    static int n;
    static int m;
    static int[][] board;
    static int[][] startend;
    static int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};
    static boolean[][] visited;
    static int cnt = 0;

    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());
        visited = new boolean[n][n];

        board = new int[n][n];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        startend = new int[m][2];
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            startend[i][0] = x-1;
            startend[i][1] = y-1;
        }

        dfs(startend[0][0], startend[0][1], 1); // 시작 위치

        System.out.println(cnt);
    }

    private static void dfs(int x, int y, int index){

        if(x == startend[index][0] && y == startend[index][1]){// 모두 다 거치고, 마지막에 도달했다면
            if(index == m-1){
                cnt++;
                return;
            }
            index++;
        }
        
        visited[x][y] = true;
        
        for(int k=0; k<4; k++){ // {{-1,0},{1,0},{0,1},{0,-1}};
            int newX = x + dir[k][0];
            int newY = y + dir[k][1];

            if(newX < 0 || newX > n-1 || newY < 0 || newY > n-1 || board[newX][newY]==1 || visited[newX][newY]){
                continue;
            }
        
        //    System.out.println(newX+","+newY);
            dfs(newX, newY, index);
        }
        
        visited[x][y] = false;
    }
}