[Softeer] Lv3. 순서대로 방문하기 (Java)

1. 문제

• 문제 링크 : Lv3. 순서대로 방문하기
• 주제 : 백트래킹

---

2. 풀이 과정 및 정리

이 문제에서는 탐색을 할 때 꼭 순서대로 방문해야하는 지점이 있다.

그래서 생각한 방법은 현재 위치에서 도착해야할 지점을 저장하여 확인하는 것이다.

동작 과정을 그림으로 표현

즉, 분홍색 지점에서 초록색 지점까지 가고 그 후 파란색 지점까지 마저 탐색할 수 있도록 한다.

 

경로 탐색 함수에서 두가지의 경우가 존재한다.

• 중간 지점에 도달한 경우 → 다음 지점까지 경로 탐색
• 마지막 도착 지점에 도달한 경우 → 경로 1개를 찾았으므로 count 증가

---

3. 코드

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

public class Main {

    static class Node {
        int x, y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    static int[][] grid;
    static boolean[][] visited;
    static Node[] order;
    static int count;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        grid = new int[n+1][n+1];
        visited = new boolean[n+1][n+1];
        order = new Node[m];
        count = 0;
        
        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= n; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            order[i] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        visited[order[0].x][order[0].y] = true;
        dfs(1, order[0]);
        bw.write(count + "");
        bw.flush();
        bw.close();
    }

    // 현재 좌표를 탐색해도 되는지 여부 판별
    static boolean isValid(int x, int y) {
        if(x < 1 || x >= grid.length || y < 1 || y >= grid.length) { //범위를 벗어날 경우
            return false;
        }
        if(grid[x][y] == 1) { //벽인 경우
            return false;
        }
        if(visited[x][y]) { //이미 방문한 경우
            return false;
        }
        return true;
    }

    static void dfs(int o, Node current) {
        //도착지점에 도달한 경우
        if(o == order.length-1 && current.x == order[o].x && current.y == order[o].y) {
            count++;
            return;
        }
        
        //중간 도착지점에 도달한 경우
        if(current.x == order[o].x && current.y == order[o].y) {
            dfs(o+1, current);
        }
        
        for(int i = 0; i < 4; i++) {
            int nx = current.x + dir[i][0];
            int ny = current.y + dir[i][1];
            if(isValid(nx, ny)) {
                visited[nx][ny] = true;
                dfs(o, new Node(nx, ny));
                visited[nx][ny] = false;
            }
        }
    }
}