[백준/자바] 7562번: 나이트의 이동

문제

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

풀이

• 체스판 위에 한 나이트가 놓여져 있다.
• 나이트가 이동하려는 칸이 주어졌을 때, 몇 번 움직이면 이동할 수 있는가?

나이트가 목적지까지 이동하는 최소 이동 횟수를 출력하라는 문제입니다.
이는 BFS를 이용해 최소 이동 횟수를 구할 수 있습니다.

	static int[][] visited;
	static final int[] dr = { -2, -1, 1, 2, -2, -1, 1, 2 };
	static final int[] dc = { -1, -2, -2, -1, 1, 2, 2, 1 };

• 이동 횟수를 이용해 방문처리를 해줄 겁니다.
• 0인 경우에는 방문하지 않은 좌표이니, 0인 경우에만 탐색을 진행했습니다.
• 나이트가 이동할 수 있는 8방 좌표를 리스트에 저장했습니다.

			n = Integer.parseInt(br.readLine());
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			sr = Integer.parseInt(st.nextToken());
			sc = Integer.parseInt(st.nextToken());
			
			st = new StringTokenizer(br.readLine());
			er = Integer.parseInt(st.nextToken());
			ec = Integer.parseInt(st.nextToken());

• 모든 입력 받은 값들을 각 변수에 저장해 줍니다.
• n: 한 변의 길이
• sr, sc: 시작 좌표
• er, ec: 도착 좌표

	private static void bfs() {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] { sr, sc }); // 시작 좌표 삽입
		visited[sr][sc] = 1; // 방문 처리 및 이동 횟수 초기화
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll(); // 현재 이동한 좌표
			int r = cur[0], c = cur[1];
			
			if (r == er && c == ec) return; // 도착했다면 리턴
			
            // 8방 탐색
			for (int i = 0; i < 8; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				
                // 범위 밖이면 continue
				if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                // 방문한 좌표라면 continue
				if (visited[nr][nc] != 0) continue;
				
                // 범위 내이면서 방문하지 않은 좌표인 경우
                // 큐에 삽입, 이동 횟수 증가(방문 처리)
				queue.add(new int[] { nr, nc });
				visited[nr][nc] = visited[r][c] + 1;
			}
		}
	}

• 전형적인 BFS 코드입니다.
• 시작 지점을 방문처리하기 위해 1로 선언하였으니, 결괏값을 출력할 땐 1을 뺀 값을 출력해야 합니다.

코드

import java.util.*;
import java.io.*;

public class Main_7562 {
	static StringBuilder sb = new StringBuilder();
	static int n, sr, sc, er, ec;
	static int[][] visited;
	
	static final int[] dr = { -2, -1, 1, 2, -2, -1, 1, 2 };
	static final int[] dc = { -1, -2, -2, -1, 1, 2, 2, 1 };
	
	private static void bfs() {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] { sr, sc });
		visited[sr][sc] = 1;
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0], c = cur[1];
			
			if (r == er && c == ec) return;
			
			for (int i = 0; i < 8; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				
				if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
				if (visited[nr][nc] != 0) continue;
				
				queue.add(new int[] { nr, nc });
				visited[nr][nc] = visited[r][c] + 1;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < t; tc++) {
			n = Integer.parseInt(br.readLine());
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			sr = Integer.parseInt(st.nextToken());
			sc = Integer.parseInt(st.nextToken());
			
			st = new StringTokenizer(br.readLine());
			er = Integer.parseInt(st.nextToken());
			ec = Integer.parseInt(st.nextToken());
			
			visited = new int[n][n];
			
			bfs();
			
			sb.append(visited[er][ec] - 1).append('\n');
			
		}
		
		System.out.println(sb.toString());
		
	}

}