BJ16948 데스나이트(JAVA 자바)

문제 출처: www.acmicpc.net/problem/16948

16948번: 데스 나이트

 

문제 유형: BFS

 

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

public class BJ16948_데스나이트 {
	static int N;
	static boolean visited[][];
	static int sx, sy, ex, ey;
	static Queue <Data> q;
	static int dr[] = {-2, -2, 0, 0, 2, 2}; 
	static int dc[] = {-1, 1, -2, 2, -1, 1};
	static class Data{
		int x;
		int y;
		int cnt;
		public Data(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		sx = Integer.parseInt(st.nextToken());
		sy = Integer.parseInt(st.nextToken());
		ex = Integer.parseInt(st.nextToken());
		ey = Integer.parseInt(st.nextToken());
		visited = new boolean[N][N];
		
		q = new LinkedList<>();
		
		visited[sx][sy] = true;
		q.offer(new Data(sx, sy, 0));
		
		Data cur = null;
		while(!q.isEmpty()) {
			cur = q.poll();
			
			if(cur.x == ex && cur.y == ey) {
				System.out.println(cur.cnt);
				System.exit(0);
			}
			
			for (int dir = 0; dir < 6; dir++) {
				int nx = cur.x + dr[dir];
				int ny = cur.y + dc[dir];
				
				if(nx < 0 || ny < 0 || nx >= N || ny >= N)
					continue;
				
				if(visited[nx][ny])
					continue;
				
				visited[nx][ny] = true;
				q.offer(new Data(nx, ny, cur.cnt + 1));
			}
		}
		System.out.println(-1);
	}
}

 

System.exit() 이 함수 사용을 자제하는 것이 좋으니 메소드로 따로 빼서 도착 지점에 도착할 경우 바로 return 해주는 방식으로 코드를 짜도 좋다. 큐에 새 객체를 넣는 과정에서 cur.cnt + 1이 아닌 cur.x + 1로 오타를 내서 20분 가량 헤맸다; 이런 자잘한 실수를 줄여야겠다.