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

문제 링크

1.

기본적인 그래프 문제였지만 요즘 문제 풀기가 너무 싫어서 뭉그적거리면서 풀었던 문제

 

 

2.

BFS를 이용하여 문제를 해결하였다.

 

나이트가 이동할 수 있는 8가지 방향을 배열로 만들어준다.

int[] dx = { 1, 2, 2, 1, -1, -2, -2, -1 };

int[] dy = { -2, -1, 1, 2, 2, 1, -1, -2 };

 

조건에 맞으면 queue에 넣는데, 중요한 점은 cnt 2차원 배열을 만들어 해당 위치까지 몇 번을 이동했는지를 저장한다.

 

 

3.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int n;
    static Pos now, goal;
    static int[][] chess;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int testCase = sc.nextInt();

        for (int t = 0; t < testCase; t++) {
            n = sc.nextInt();
            chess = new int[n][n];

            now = new Pos(sc.nextInt(), sc.nextInt());
            goal = new Pos(sc.nextInt(), sc.nextInt());

            if (now.equals(goal)) {
                System.out.println("0");
            } else {
                System.out.println(bfs());
            }
        }
        sc.close();
    }

    static int bfs() {
        boolean[][] visited = new boolean[n][n];
        Queue<Pos> q = new LinkedList<>();
        int[] dx = { 1, 2, 2, 1, -1, -2, -2, -1 };
        int[] dy = { -2, -1, 1, 2, 2, 1, -1, -2 };
        int[][] cnt = new int[n][n];

        q.offer(now);
        visited[now.x][now.y] = true;
        while (!q.isEmpty()) {
            Pos temp = q.poll();
            if (temp.equals(goal)) {
                return cnt[temp.x][temp.y];
            }

            for (int i = 0; i < 8; i++) {
                int nx = temp.x + dx[i];
                int ny = temp.y + dy[i];

                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    if (!visited[nx][ny]) {
                        visited[nx][ny] = true;
                        cnt[nx][ny] = cnt[temp.x][temp.y] + 1;
                        q.offer(new Pos(nx, ny));
                    }
                }
            }
        }
        return 0;
    }
}

class Pos {
    int x, y;

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

    @Override
    public boolean equals(Object obj) {
        Pos p = (Pos) obj;
        if (x == p.x && y == p.y) {
            return true;
        } else {
            return false;
        }
    }
}

 

 

4.

Pos 클래스의 변수들이 같은지 확인할 때 단순히 == 를 사용하여도 무관하지만, 코드의 간결함을 위해 equals 메소드를 오버라이드 하였다. 위의 코드 마지막 부분을 참고하자.

 

 

[참고] https://ukyonge.tistory.com/87