[백준, 자바, 7562번] 나이트의 이동

풀이

• 해당 문제는 SSAFY에서 몇 번 접했던 문제로
• 그냥 기존 4방향으로 가는 걸, 8방향으로 만들어서 적용.
• 다만, ㅋㅋㅋ 오랜만에 알고리즘을 풀다보니
• 위로 가는걸 음수가 아닌 양수로 더하다보니
• 뭔가 의도대로 안되는 걸 조금 늦게 확인함...
• 다른 건 다 유사한 형태의 문제라서 풀이는 생략.

 

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


public class _7562 {
    static int l;
    static int[] start;
    static int[] end;
    static int[] ni = {-2,-1,1,2,2,1,-1,-2};
    static int[] nj = {1,2,2,1,-1,-2,-2,-1};
    static int[][] mtx;
    static boolean[][] visit;
    static Deque<List<Integer>> dq;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int tc = Integer.parseInt(br.readLine());
        for (int t=0; t<tc; t++) {
            l = Integer.parseInt(br.readLine());
            mtx = new int[l][l];
            visit = new boolean[l][l];
            start = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            end = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            bw.write(dfs(0)+"\n");
        }
        bw.flush();
    }

    public static int dfs(int cnt) {
        dq = new ArrayDeque<>(List.of(new ArrayList<>(Arrays.asList(start[0],start[1],cnt))));
        visit[start[0]][start[1]] = true;
        while (!dq.isEmpty()) {
            List<Integer> li = dq.pollFirst();
            if (li.get(0)==end[0] && li.get(1)==end[1]) return li.get(2);

            for (int k=0; k<8; k++) {
                int di = li.get(0)+ni[k];
                int dj = li.get(1)+nj[k];
                if ((0<=di&&di<l) && (0<=dj&&dj<l) && !visit[di][dj]) {
                    dq.addLast(new ArrayList<>(Arrays.asList(di,dj,li.get(2)+1)));
                    visit[di][dj] = true;
                }
            }
        }
        return cnt;
    }
}