공부 189일차: 백준 7562번 나이트의 이동 자바 java

7562 나이트의 이동

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

7562번: 나이트의 이동

 

 

 

---

백준 7562번 문제 나이트의 이동

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	45566	23188	17264	49.835%

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

제한

 

예제 입력 1

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1

5
28
0

힌트

 

 

 

 

---

과정 생각해보기 & 오답

---

 

최단거리, 최솟값 => BFS

이렇게 8방향으로 움직여야 한다는 것만 알면 쉬운 문제다

https://gimbalja.tistory.com/339

공부 187일차: 백준 2178번 미로 탐색 자바 java

이 문제와 유사!

 

 

 

---

정답 인정 코드

---

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int testCase, l, startX, startY, goalX, goalY;
    static int[][] matrix;
    static boolean[][] visited;
    static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
    static int[] dy = {-1, 1, 2, -2, -2, 2, -1, 1};
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        testCase = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < testCase; i++) {
            l = Integer.parseInt(br.readLine());
            matrix = new int[l][l];
            visited = new boolean[l][l];
            // 시작
            st = new StringTokenizer(br.readLine());
            startX = Integer.parseInt(st.nextToken());
            startY = Integer.parseInt(st.nextToken());
            // 목적지
            st = new StringTokenizer(br.readLine());
            goalX = Integer.parseInt(st.nextToken());
            goalY = Integer.parseInt(st.nextToken());
            
            BFS(startX, startY);
            System.out.println(matrix[goalX][goalY]);
        }
    }
 
    static void BFS(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x, y));
        visited[x][y] = true;    // 방문처리
        
        while(!q.isEmpty()) {    
            Node next = q.poll();
            if(next.x == goalX && next.y == goalY) {
                return;    // 목적지에 도착했다면
            }
            for(int i = 0; i < 8; i++) {    // 나이트가 이동할 수 있는 8방향
                int X = next.x + dx[i];
                int Y = next.y + dy[i];
                
                if(X > -1 && X < l && Y > -1 && Y < l) {    // 범위 
                    if(!visited[X][Y]) {
                        q.add(new Node(X, Y));
                        visited[X][Y] = true;
                        matrix[X][Y] = matrix[next.x][next.y] + 1;
                    }
                }
            }
        }
    }
 
    static class Node{
        int x, y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
 

 

 

 

---