[백준] 16948 데스 나이트 - BFS JAVA

https://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 Main {
	
	public static int N, M;
	public static int[] dx = {-2,-2,0,0,2,2};
	public static int[] dy = {-1,1,-2,2,-1,1};
	public static boolean[][] visited;
	public static Node firstNode = null, secondNode = null;
	public static int answer = -1;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
		int r1 = Integer.parseInt(st.nextToken());
		int c1 = Integer.parseInt(st.nextToken());
		int r2 = Integer.parseInt(st.nextToken());
		int c2 = Integer.parseInt(st.nextToken());
    	firstNode = new Node(r1, c1, 0);
    	secondNode = new Node(r2, c2, 0);
    	
		simulate(firstNode);
    	
    	if(answer > -1)System.out.println(answer);
    	else System.out.println(answer);
    }
    
    public static void simulate(Node start) {
    	Queue<Node> q = new LinkedList<Node>();
    	q.offer(start);
    	visited = new boolean[N][N];
    	visited[start.r][start.c] = true;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int r= temp.r;
    		int c = temp.c;
    		int cnt = temp.cnt;
    		for(int dir=0;dir<6;dir++) {
    			int nr = r + dx[dir];
    			int nc = c + dy[dir];
    			if(nr < 0 || nr >= N || nc < 0 || nc>= N) continue;
    			if(visited[nr][nc] == true) continue;
    			
    			if(nr == secondNode.r && nc == secondNode.c) {
    				answer = cnt + 1;
    				return ;
    			}
    			visited[nr][nc] = true;
    			q.offer(new Node(nr, nc, cnt + 1));
    		}
    		
    	}
    	
    }
    
    
    
}

class Node{
	int r;
	int c;
	int cnt;
	public Node(int r, int c,int cnt) {
		this.r=r;
		this.c=c;
		this.cnt=cnt;
	}
}