백준 7562 나이트의 이동

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

백준 7562번 나이트의 이동

가볍게 BFS를 통해 해결할 수 있는 문제입니다!

 

기존의 BFS 문제를 해결할때 사용하던 Delta X, Delta Y 배열에

상하 좌우가 아닌 나이트의 이동이 가능한 방향인 8방향을 넣고 BFS를 진행하니

간단하게 시작점에서 도착점까지의 최소 구간을 구해낼 수 있었습니다.

 

아래는 코드입니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class MyPoint {
	int y, x;
	public MyPoint(int y, int x) {
		this.y = y;
		this.x = x;
	}
}
public class Knight {
	static int[][] map;
	static boolean[][] isNotVisted;
	static Queue<MyPoint> mapQueue = new LinkedList<>();
	static int[] dirx = {1,2,2,1,-1,-2,-2,-1};
	static int[] diry = {-2,-1,1,2,2,1,-1,-2};
	static int n;
	
	public static void main(String[] args) throws IOException{
		int tcNum, i, j;
		// TODO Auto-generated method stub
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		tcNum = Integer.parseInt(st.nextToken());
		int y, x;
		MyPoint startP, finishP;
		for(i = 0; i<tcNum; i++) {
			st = new StringTokenizer(bf.readLine());
			n = Integer.parseInt(st.nextToken());
			
			map = new int[n][n];
			isNotVisted = new boolean[n][n];
			for(j = 0; j<n; j++)
				Arrays.fill(isNotVisted[j], true);
			
			st = new StringTokenizer(bf.readLine());
			y = Integer.parseInt(st.nextToken());
			x = Integer.parseInt(st.nextToken());
			
			startP = new MyPoint(y, x);
			
			st = new StringTokenizer(bf.readLine());
			y = Integer.parseInt(st.nextToken());
			x = Integer.parseInt(st.nextToken());
			finishP = new MyPoint(y, x);
			
			System.out.println(bfsKnight(startP, finishP));
		}
	}
	public static void printMap() {
		int i, j;
		for(i=0; i<n; i++) {
			for(j=0; j<n; j++) {
				if(isNotVisted[i][j])
					System.out.print("t ");
				else
					System.out.print("f ");
			}
			System.out.println();
		}
		System.out.println();
	} 
    
	public static int bfsKnight(MyPoint s, MyPoint f) {
		int len, count = -1;
		int i, j, y, x;
		MyPoint tmp;
		isNotVisted[s.y][s.x] = false;
		mapQueue.add(s);
		while(!mapQueue.isEmpty()) {
			count++;
			
			if(!isNotVisted[f.y][f.x])
				break;
			
			len = mapQueue.size();
			for(i=0; i<len; i++) {
				tmp = mapQueue.remove();
				
				for(j=0; j<8; j++) {
					y = tmp.y + diry[j];
					x = tmp.x + dirx[j];
					
					if(y>= 0 && y<n && x>=0 && x<n && isNotVisted[y][x]) {
						isNotVisted[y][x] = false;
						mapQueue.add(new MyPoint(y, x));
					}
				}
			}
		}
		mapQueue.clear(); //! 큐큐큐 비우는거 잊지 말기!!!
		
		return count;
	}

}

 

실수한 점

• 이전에 진행한 큐가 초기화 되지 않아 다음 테스트 케이스를 진행할 때 영향을 주었음! 이를 주의하자!