[소프티어] [HSAT 7회 정기 코딩 인증평가 기출] 순서대로 방문하기(JAVA)

문제

https://softeer.ai/practice/6246

---

풀이(19분)

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

public class Main {

    // dfs로 하면서 추적하자.
    // m의 포인트를 리스트로 관리하고, 지도상에는 2로 표시하자.
    // 만약 dfs 이동 중에 2를 만난다면 현재 포인트 인덱스와 일치하는지를 판단하자.
    // 아니라면 리턴을 해주어야 한다!

    static int n, m, answer;
    static int[][] map;
    static boolean[][] visited;
    static Point[] order;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        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];
        order = new Point[m];

        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 row = Integer.parseInt(st.nextToken()) - 1;
            int col = Integer.parseInt(st.nextToken()) - 1;
            map[row][col] = 2;
            order[i] = new Point(row, col);
        }

        dfs(order[0], 0);

        System.out.println(answer);
    }

    static void dfs(Point p, int depth){
        int nowRow = p.row;
        int nowCol = p.col;

        visited[nowRow][nowCol] = true;

        // 이 칸이 2이고, 현재 순서대로 가야 하는 포인트라면
        if(map[nowRow][nowCol] == 2){
            if(depth >= m || nowRow != order[depth].row || nowCol != order[depth].col){
                visited[nowRow][nowCol] = false; // 빠르게 백트래킹
                return;
            }
            depth++; // 올바른 순서의 포인트일 경우에만 증가
        }

        // 모든 포인트를 순서대로 방문했으면 성공!
        if(depth == m){
            answer++;
            visited[nowRow][nowCol] = false;
            return;
        }

        for(int i = 0; i < 4; i++){
            int nextRow = nowRow + dx[i];
            int nextCol = nowCol + dy[i];
            if(isBounds(nextRow, nextCol)){
                if(!visited[nextRow][nextCol] && map[nextRow][nextCol] != 1){
                    dfs(new Point(nextRow, nextCol), depth);
                }
            }
        }

        visited[nowRow][nowCol] = false; // 백트래킹
    }


    static boolean isBounds(int row, int col){ // 격자 범위 안에 있는지 확인
        return row >= 0 && row < n && col >= 0 && col < n;
    }

    static class Point{

        int row, col;
        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

---

문제 풀이 전략

 

dfs를 통해 경로를 계산한다. map에는 2라는 값을 방문해야하는 지점으로 체크한다.

[도구정리] DFS, BFS

경로를 따라갈 때, 방문해야 하는 지점을 depth로 정해두고 이를 만족하는지 확인한다.

확인하는 과정에서 순서에 어긋난다면 백트래킹과 return을 즉각적으로 해준다.

 

최종적으로 도착해야하는 포인트에 도착했다면 정답을 +1 해준다.