[Silver I] 나이트의 이동 - 7562

문제 링크

성능 요약

메모리: 114936 KB, 시간: 380 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 6월 30일 03:49:27

문제 설명

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

입력

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

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

출력

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

BFS 풀이

나이트가 움직일 수 있는 경로를 미리 배열로 정해놓고, BFS 알고리즘을 실행하면 된다.
[나이트의 이동] 해당 강의를 참고했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	//BFS 알고리즘 사용
	static int[] d8i = {2,1,-1,-2,-2,-1,1,2}; //나이트가 움직일 수 있는 경로
	static int[] d8j = {1,2,2,1,-1,-2,-2,-1};
	
	static int[][] chessMap; //체스판 2차원 배열
	static int I; //체스판 크기
	static boolean[][] visited;//방문 여부 확인
	
	static int start_i; static int start_j; //시작 위치
	static int end_i; static int end_j; //도착 위치
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder(); //입력 , 출력 용도
		
		int n =  Integer.parseInt(br.readLine()); //테스트케이스 입력받기
		
		for(int i=0; i<n; i++) {
			I = Integer.parseInt(br.readLine());
			chessMap = new int[I][I];
			visited=  new boolean[I][I];
			
			st = new StringTokenizer(br.readLine());
			start_i = Integer.parseInt(st.nextToken());
			start_j = Integer.parseInt(st.nextToken());
			
			st = new StringTokenizer(br.readLine());
			end_i = Integer.parseInt(st.nextToken());
			end_j = Integer.parseInt(st.nextToken());
			
			
			BFS(); //BFS 실행
			
			sb.append(chessMap[end_i][end_j]+"\n"); //해당 결과 저장
		}
		
		System.out.println(sb.toString()); //결과 출력
	}
	
	public static void BFS() {
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] {start_i,start_j});
		visited[start_i][start_j]=true;
		
		while(!queue.isEmpty()) {
			int[] now = queue.poll();
			int nx = now[0];
			int ny = now[1];
			
			for(int i=0; i<8; i++) {
				int tx = nx + d8i[i];
				int ty = ny + d8j[i];
				
				if(tx < 0 || ty < 0 || tx>=I || ty >= I) { //범위 벗어날 경우 X
					continue;
				}
				if(visited[tx][ty]) { //이미 방문했을 경우 X
					continue;
				}
				queue.add(new int[] {tx,ty});
				chessMap[tx][ty] = chessMap[nx][ny]+1;
				visited[tx][ty]=true;		
			}
		}
	}
}