(JAVA) 백준 7562번 : 나이트의 이동

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

7562번: 나이트의 이동

 

BFS를 사용하는 문제이다.

 

차이점은 자기 자리에서 이동할 수 있는 경우의 수가 8가지 라는 점..?

 

하지만 다른 사람들보다 계산 방식은 비슷한데

시간이 더 걸리는 이유가 무엇인지 모르겠다...

 

아.. 그리고 boolean 2차원 배열로 좌표 방문 여부를 체크했다.

우선순위 큐를 사용했기 때문에 무조건 최소인 경우에 처음으로 방문한 것이 되니까!

 

** 의문으로 남은 점

 - 굳이 우선순위 큐를 사용하지 않아도 되나?

 - 시간이 오래 걸리는 이유가...ㅠㅠㅠ

 

소스 코드

---

package dfsnfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// 나이트의 이동 문제
// BFS 사용하기
public class p7562 {
	static int[][] distanceMap;
	static boolean[][] visited;
	static int[] moveX = {1, 2, 2, 1, -1, -2, -2, -1};	// 시계 방향 순서
	static int[] moveY = {-2, -1, 1, 2, 2, 1, -1, -2};
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int tc = Integer.valueOf(st.nextToken());
		StringBuilder sb = new StringBuilder();
		
		while(tc --> 0) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.valueOf(st.nextToken());
			distanceMap = new int[n][n];
			visited = new boolean[n][n];
			
			st = new StringTokenizer(br.readLine());
			int startX = Integer.valueOf(st.nextToken());
			int startY = Integer.valueOf(st.nextToken());
			st = new StringTokenizer(br.readLine());
			int endX = Integer.valueOf(st.nextToken());
			int endY = Integer.valueOf(st.nextToken());
			
			int result = bfs(n, startX, startY, endX, endY);
			sb.append(result).append("\n");
		}
		System.out.println(sb.toString());
	}
	private static int bfs(int n, int startX, int startY, int endX, int endY) {
		PriorityQueue<Point7562> queue = new PriorityQueue<Point7562>();
		queue.offer(new Point7562(startX, startY, 0));
		visited[startY][startX] = true;
		
		while(!queue.isEmpty()) {
			Point7562 currentPoint = queue.poll();
			int currentX = currentPoint.x;
			int currentY = currentPoint.y;
			if(currentX == endX && currentY == endY) {
				return currentPoint.count;
			}
			
			for(int i = 0; i < moveX.length; i++) {
				int nextX = currentX + moveX[i];
				int nextY = currentY + moveY[i];
				if((nextX < 0 || nextX >= n) || (nextY < 0 || nextY >= n)) {	// 체스 판 범위 내 여야 함.
					continue;
				}
				if(visited[nextY][nextX])
					continue;
				// 한 번도 방문 안한 좌표 점의 count
				if(distanceMap[nextY][nextX] == 0 || currentPoint.count + 1 < distanceMap[nextY][nextX]) {
					distanceMap[nextY][nextX] = currentPoint.count + 1;
					visited[nextY][nextX] = true;
					queue.offer(new Point7562(nextX, nextY, distanceMap[nextY][nextX]));
				}
			}
		}
		return distanceMap[endY][endX];
	}
}

class Point7562 implements Comparable<Point7562> {
	int x;
	int y;
	int count;
	
	Point7562(int x, int y, int count) {
		this.x = x;
		this.y = y;
		this.count = count;
	}

	@Override
	public int compareTo(Point7562 o) {
		if(this.count < o.count ) {	// 오름차순
			return -1;
		}
		else
			return 1;
	}
	
}

 

 

이상입니다.

 

감사합니다!