[백준] 7562 : 나이트의 이동

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

소요 시간 : 풀이(1h)

---

문제

---

풀이

 

바로 이전 문제인 `백준 1697: 숨바꼭질`의 풀이법과 동일해서 어떻게 풀어야하는지는 바로 알았다.

 

대신 저번 문제는 무력하게 다른 답안을 참고해서 풀었기 때문에 이전에 푼 풀이를 그대로 하드코딩하는 건 무용하다고 생각해 내가 스스로 점검해나가며 풀어보려고 시간이 좀 걸렸다.

 

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

public class Main {

    private static int[][] board;
    private static final int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
    private static final int[] dy = {-1, -2, -2, -1, 1, 2, 2, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testcase = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while (testcase-- > 0) {
            int l = Integer.parseInt(br.readLine()); // 4 ~ 300
            board = new int[l][l];

            Point start = new Point(new StringTokenizer(br.readLine()));
            Point end = new Point(new StringTokenizer(br.readLine()));

            sb.append(bfs(start, end)-1).append("\n");
        }

        System.out.print(sb);
    }

    public static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        Point(StringTokenizer st) {
            this.x = Integer.parseInt(st.nextToken());
            this.y = Integer.parseInt(st.nextToken());
        }
    }

    private static int bfs(Point start, Point end) {
        board[start.x][start.y] = 1;
        Queue<Point> queue = new ArrayDeque<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            for (int idx = 0; idx < dx.length; idx++) {
                int knight_x = point.x + dx[idx];
                int knight_y = point.y + dy[idx];

                if (knight_x < 0 || knight_y < 0 || knight_x >= board.length || knight_y >= board.length) continue;

                if (board[knight_x][knight_y] == 0) {
                    if (knight_x == end.x && knight_y == end.y) return board[point.x][point.y] + 1;

                    board[knight_x][knight_y] = board[point.x][point.y] + 1;
                    queue.add(new Point(knight_x, knight_y));
                }
            }
        }

        return board[end.x][end.y];
    }
}

 

 

이전에 BFS 문제를 풀면서 아쉬웠던 좌표를 가진 지점에 대한 클래스 Point를 만들고 그것을 Queue에 저장하는 식을 문제를 해결했다.

 

문제를 풀고 좋은 풀이를 찾아 다른 사람의 풀이를 찾아보니 최단 208 ms에 메모리 사용량도 나보다 20000 kb 이상 적은 경우가 있어 무엇이 다른가 확인했는데, 나는 Queue 인터페이스를 LinkedList로 구현한 반면, 다른 사람은 Deque를 통해 소요 시간과 메모리 사용량을 모두 낮춘 것을 확인했다.

 

상: DequeArray, 하: LinkedList

 

그래서 다른 부분은 그대로 두고 LinkedList만을 DequeArray로 바꾸니 성능과 시간 모두 훨씬 좋아지는 것을 확인할 수 있었다.