[백준/java] 7562번 : 나이트의 이동(체스 나이트의 이동) - BFS

7562번 : 나이트의 이동

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

7562번: 나이트의 이동

728x90

 

7562번 : 나이트의 이동

 

토마토 문제처럼 이번 문제도 Queue에 넣는 클래스가 y, x값 말고도 cnt가 하나 더 들어갔다.

이것의 용도는 최단거리를 측정할 때 사용하는 것!

이제 점점 BFS로 순회할 때 최단거리를 계산하는 방법이 조금씩 감이 오는 것 같다.

 

반응형

 

이 문제에서 int형 이차원 배열이 따로 사용되지는 않았다.

방문하는 곳마다 값을 확인할 필요가 없었기 때문이다.

 

이 문제를 풀때 오래걸리고 오해했던 것은

도착지로 갈 때, 이동할 때마다 거리를 계산해서 더욱 가까운곳으로 계산하는 로직을 추가했었다.

그런데 이 로직은 쓸 데 없었다.

어짜피 이동하는 방법은 BFS 로직이 찾아줄거고, 최소 횟수를 찾아 주는 것은 cnt 변수값을 다루는 부분이 해준다.

 

package bfs;

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

public class MovingOfNight {
	static boolean[][] visit;
	static int[] dx = {1, 2, 2, 1, -1, -2, -2, -1};
	static int[] dy = {-2, -1, 1, 2, 2, 1, -1, -2};
	static int N;
	static class Night {
		int y, x, cnt;
		
		public Night(int y, int x, int cnt) {
			this.y = y;
			this.x = x;
			this.cnt = cnt;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = stoi(br.readLine());
		
		while(T-- > 0) {
			N = stoi(br.readLine());
			visit = new boolean[N][N];
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			int nightY = stoi(st.nextToken());
			int nightX = stoi(st.nextToken());
			
			st = new StringTokenizer(br.readLine(), " ");
			int destY =  stoi(st.nextToken());
			int destX =  stoi(st.nextToken());
			
			int min = Integer.MAX_VALUE;
			
			visit[nightY][nightX] = true;
			int cnt = 0;
			
			Queue<Night> q = new LinkedList<Night>();
			q.add(new Night(nightY, nightX, 0));
			while(!q.isEmpty()) {
				Night cur = q.poll();
				
				if(cur.y == destY && cur.x == destX) {
					min = Math.min(min, cur.cnt);
					break;
				}
				
				for (int dir = 0; dir < 8; dir++) {
					int ny = cur.y + dy[dir];
					int nx = cur.x + dx[dir];
					
					if(ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
					if(visit[ny][nx]) continue;
					
					visit[ny][nx] = true;
					cnt = cur.cnt + 1;
					
					q.add(new Night(ny, nx, cnt));
				}
			}
			
			bw.write(min + "\n");
		}
		
		bw.flush();
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
}