[소프티어] 6246번 - 순서대로 방문하기 [Java]

https://softeer.ai/practice/6246

 

[소프티어] 6246번 - 순서대로 방문하기 [Java]

[소프티어] 6246번 - 순서대로 방문하기 [Java]

[소프티어] 6246번 - 순서대로 방문하기 [Java]

[소프티어] 6246번 - 순서대로 방문하기 [Java]

[소프티어] 6246번 - 순서대로 방문하기 [Java]

---

1.  아이디어

 

N의 크기가 매우 작은 문제로 DFS 알고리즘을 활용하면 해결할 수 있는데 이때 방문해야하는 순서를 지키면서 모두 방문을 해야한다. 이를 위해 주어진 맵과 같은 크기의 맵에 방문해야하는 위치에 방문 순서를 저장한 pathOrder 2차원 배열을 활용해서 DFS에서 다음에 방문할 장소가 방문해야하는 지점이 아니면 일반 DFS를 적용하고 방문해야하는 장소면 순서가 맞는지 고려하는 방식으로 해결했다.

---

2. 문제풀이

 

모든 경로를 탐색하기 위해 방문 체크 후 방문 체크 해제를 하는 DFS를 적용했다. 사방탐색을 하며 맵 바깥이거나 벽이거나 방문한 곳이면 넘어갔는데 그러면 탐색할 수 있는 장소는 일반 장소거나 방문해야하는 장소 두가지가 남는다. 이때 일반 장소면 그냥 방문하고 방문해야하는 장소는 순서가 맞으면 방문하도록 했는데 이 비교는 파라미터로 현재 가장 최근에 방문한 방문해야하는 장소를 들고 다니며 비교하는 방식으로 구현했다.

---

3. 코드

 

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

public class Main {

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};

    private static int N;
    private static int M;
    private static int[][] map;
    private static boolean[][] visited;

    // 방문해야하는 지점의 순서를 기록하는 2차원 배열
    private static int[][] pathOrder;
    private 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());

        map = new int[N][N];
        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());
            }
        }

        visited = new boolean[N][N];
        pathOrder = new int[N][N];
        int[] start = new int[2];

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            pathOrder[r][c] = i;

            if (i == 1) {
                start[0] = r;
                start[1] = c;
            }
        }

        // 시작 지점에서 탐색을 시작하며 가장 최근에 방문한 방문해야하는 지점을 order 파라미터로 들고 다님
        dfs(start[0], start[1], 1);

        System.out.println(cnt);
    }

    private static void dfs(int r, int c, int order) {
        visited[r][c] = true;

        // 모든 지점을 방문한 경우
        if (order == M) {
            cnt++;
            return;
        }

        for (int dir = 0; dir < 4; dir++) {
            int nr = r + dr[dir];
            int nc = c + dc[dir];

            if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
            if (map[nr][nc] == 1 || visited[nr][nc]) continue;

            // 방문해야하는 지점이 아니면 그냥 방문하고 방문해야하는 지점이면 순서가 맞을 경우 방문
            if (pathOrder[nr][nc] == 0) {
                dfs(nr, nc, order);
            } else if (pathOrder[nr][nc] == order + 1) {
                dfs(nr, nc, order + 1);
            }

            // 방문 체크 해제로 모든 방문 가능한 경로 탐색
            visited[nr][nc] = false;
        }
    }

}

---

4. 후기