[백준] 7562 나이트의 이동 자바 BFS 문제 풀이 및 정답

문제 요약)

- 나이트의 위치가 주어지고 8방향으로 이동이 가능

- 시작점부터 도착지점까지의 이동 거리 출력

 

주의점)

- 8방향 좌표만 잘 기억하면 큰 어려움 x

 

풀이)

보통은 4방향 탐색을 많이 하는데 약간 응용해서

8방향으로 탐색을 하는 문제이기에 방향만 잘 정해서

8방향 탐색루프를 돌며 bfs 진행

 

정답)

*Scanner 대신 bufferedReader를 사용하면 시간을 더 줄일 수 있습니다.

java

닫기 줄바꿈

import java.util.*;

public class KnightMove7562_blog {
​​​​static int[] dx = {-1, -2, -2, -1, 1, 2, 2, 1}; // 8방향 탐색
​​​​static int[] dy = {-2, -1, 1, 2, 2, 1, -1, -2};
​​​​static int t;
​​​​static int n;
​​​​static int[][] map;

​​​​public static void main(String[] args) {
​​​​​​​​Scanner sc = new Scanner(System.in);
​​​​​​​​t = sc.nextInt();
​​​​​​​​
​​​​​​​​for (int i = 0; i< t; i++) {
​​​​​​​​​​​​n = sc.nextInt();
​​​​​​​​​​​​map = new int[n][n];

​​​​​​​​​​​​int beginX = sc.nextInt();
​​​​​​​​​​​​int beginY = sc.nextInt();

​​​​​​​​​​​​int endX = sc.nextInt();
​​​​​​​​​​​​int endY = sc.nextInt();

​​​​​​​​​​​​BFS(beginX, beginY);
​​​​​​​​​​​​System.out.println(map[endX][endY] - 1); // 1로 시작했기 때문에 -1 해주기
​​​​​​​​}
​​​​}

​​​​static void BFS(int x, int y) {
​​​​​​​​Queue<int[]> q = new LinkedList<>();
​​​​​​​​q.offer(new int[] {x, y});
​​​​​​​​map[x][y] = 1; // 1로 해줘야 방문한곳 판단이 쉬워서

​​​​​​​​while(!q.isEmpty()) {
​​​​​​​​​​​​int[] current = q.poll();
​​​​​​​​​​​​for (int i=0; i<dx.length; i++) {
​​​​​​​​​​​​​​​​int nextX = current[0] + dx[i];
​​​​​​​​​​​​​​​​int nexY = current[1] + dy[i];

​​​​​​​​​​​​​​​​// out of index 방지, 이미 방문한 곳 제외
​​​​​​​​​​​​​​​​if (nextX < 0 || nextX >= n || nexY < 0 || nexY >= n) continue;
​​​​​​​​​​​​​​​​if (map[nextX][nexY] > 0) continue;

​​​​​​​​​​​​​​​​q.offer(new int[] {nextX, nexY});
​​​​​​​​​​​​​​​​map[nextX][nexY] = map[current[0]][current[1]] + 1;
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}
}