99클럽 코테 스터디 9일차(DFS)

문제 : https://www.acmicpc.net/problem/7562

제한조건

• 나이트의 이동 가능 거리(총 3칸)
  = 2칸(좌/우), 1칸(상/하)
  = 1칸(좌/우), 2칸(상/하)

🚨오늘의 학습

⭐️DFS⭐️

나이트의 하나의 위치(현재 위치)에서 도달 가능한 모든 위치를 깊이 우선 탐색(DFS)으로 재귀적으로 탐색하도록 구현

🗝️ 각 위치에서 이동할 수 있는 경우의 수 8가지

🗝️ dx/dy 알리고리즘 = 좌표상 방향(E->S->W->N)

---

• 첫번째 시도 : 시간초과

import static java.lang.Integer.MAX_VALUE;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[] dx = new int[]{1, 0, -1, 0};
    static int[] dy = new int[]{0, -1, 0, 1};
    static int answer;
    static boolean[][] visited;

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

        int cnt = Integer.parseInt(st.nextToken());

        for (int i = 0; i < cnt; i++) {
            answer = MAX_VALUE;
            st = new StringTokenizer(br.readLine());

            int size = Integer.parseInt(st.nextToken());

            // 방문 여부 체크를 위한 2차원 boolean 배열 초기화
            visited = new boolean[size][size];

            st = new StringTokenizer(br.readLine());
            int[] startPoint = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};

            st = new StringTokenizer(br.readLine());
            int[] endPoint = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};

            dfs(startPoint, endPoint, 1, 0, 2, 1, size, 0);
            dfs(startPoint, endPoint, 1, 0, 1, 2, size, 0);
            dfs(startPoint, endPoint, 1, 2, 2, 1, size, 0);
            dfs(startPoint, endPoint, 1, 2, 1, 2, size, 0);
            dfs(startPoint, endPoint, 3, 0, 2, 1, size, 0);
            dfs(startPoint, endPoint, 3, 0, 1, 2, size, 0);
            dfs(startPoint, endPoint, 3, 2, 2, 1, size, 0);
            dfs(startPoint, endPoint, 3, 2, 1, 2, size, 0);

            System.out.println(answer);
        }
    }

    public static void dfs(int[] start, int[] end, int sn, int lf, int snMove, int lfMove, int size, int step) {
        if (start[0] == end[0] && start[1] == end[1]) {
            answer = Math.min(answer, step);
            return;
        }

        if (step >= answer || start[0] < 0 || start[0] >= size || start[1] < 0 || start[1] >= size || visited[start[0]][start[1]]) {
            return;
        }

        // 현재 위치를 방문했음으로 표시
        visited[start[0]][start[1]] = true;

        // 다음 위치로 이동
        int[] startPoint = new int[]{start[0] + (dx[lf] * lfMove), start[1] + (dy[sn] * snMove)};

        dfs(startPoint, end, 1, 0, 2, 1, size, step + 1);
        dfs(startPoint, end, 1, 0, 1, 2, size, step + 1);
        dfs(startPoint, end, 1, 2, 2, 1, size, step + 1);
        dfs(startPoint, end, 1, 2, 1, 2, size, step + 1);
        dfs(startPoint, end, 3, 0, 2, 1, size, step + 1);
        dfs(startPoint, end, 3, 0, 1, 2, size, step + 1);
        dfs(startPoint, end, 3, 2, 2, 1, size, step + 1);
        dfs(startPoint, end, 3, 2, 1, 2, size, step + 1);

        // 백트래킹을 위해 방문 여부를 해제
        visited[start[0]][start[1]] = false;
    }
}