백준 7562번 - 나이트의 이동 / Java

문제

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

7562번: 나이트의 이동

BFS탐색 문제 한 번에 뻗어 나가는 범위가 8개다. 그 부분만 유의하면서 탐색하면 어렵지 않은 문제

 

알고리즘

1. 시작할 때 현재 위치와 목적지가 같다면 바로 0을 출력하고 다음 케이스로 넘어간다

2. BFS탐색을 시작한다. 큐의 크기만큼만 탐색하고 횟수를 1 늘린다

3. 2번을 반복한다. 탐색 중 목적지가 나오면 현재 횟수를 출력하고 종료한다

소스코드

/*
 * BOJ7562
 * 2020.01.24
 * Hyeonseong
 */
import java.util.*;
public class BOJ7562
{
    public static void main(String[] args) 
    {
        Solution s = new Solution();
    }
}
class Node{
    int x;
    int y;
    Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}
class Solution{
    int t; // 테스트케이스 수
    int n; // 체스판길이
    int board[][]; // 체스판
    boolean visit[][]; 
    Node start; // 시작하는 곳
    Node end; // 끝나는 곳
    Queue<Node> q;
    int answer; // 정답
    public Solution() {
        Scanner scan = new Scanner(System.in);
        t = scan.nextInt();
        while(t-->0) {
            n = scan.nextInt();
            board = new int[n][n];
            visit = new boolean[n][n];
            for(int i=0;i<n;i++) {
                board[i] = new int[n];
                visit[i] = new boolean[n];
            }
            start = new Node(scan.nextInt(),scan.nextInt());
            end = new Node(scan.nextInt(),scan.nextInt());
            q = new LinkedList<Node>();
            if(start.x==end.x && start.y == end.y) { // 시작위치와 목적지가 같다면 바로0을출력
                System.out.println("0");
                continue;
            }
            answer = 0;
            q.offer(start); // 시작위치를 큐에 넣고 탐색 시작
            visit[start.x][start.y] = true;
            while(!q.isEmpty()) {
                if(bfs(q.size())) { // true가 리턴되면 목표지점을 찾은거니까 break;
                    answer++;
                    break;
                }
                answer++;
            }
            System.out.println(answer);
        }
    }
    public boolean bfs(int num) { // 횟수를 세기위해 큐의 크기만큼만 poll 한다
        int di[] = {-2,-2,-1,-1,1,1,2,2};
        int dj[] = {-1,1,-2,2,-2,2,-1,1};
        while(num-->0) {
            Node temp = q.poll();
            for(int i=0;i<8;i++) {
                int dx = temp.x+di[i];
                int dy = temp.y+dj[i];
                if(dx>=0 && dy>=0 && dx<n && dy<n && !visit[dx][dy]) {
                    if(dx == end.x && dy == end.y) {
                        return true;
                    }
                    else {
                        q.offer(new Node(dx,dy));
                        visit[dx][dy] = true;
                    }
                }
            }
        }
        return false;
    }
}