백준 7562번: 나이트의 이동 [BFS][탐색][그래프] -Java

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

7562번: 나이트의 이동

 

 

<Java 코드>

import java.io.BufferedReader;
import java.io.FileInputStream;
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 void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int T = Integer.parseInt(st.nextToken());

		int dx[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
		int dy[] = { -2, -1, 1, 2, 2, 1, -1, -2 };

		for (int tc = 0; tc < T; tc++) {
			int L = Integer.parseInt(br.readLine());

			int map[][] = new int[L][L];
			int visit[][] = new int[L][L]; //해당 칸에 방문하기까지 이동한 횟수

			//현재 나이트의 위치
			st = new StringTokenizer(br.readLine());
			Pos cur = new Pos(Integer.parseInt(st.nextToken()),
					Integer.parseInt(st.nextToken()));
			
			//이동하려는 나이트 위치
			st = new StringTokenizer(br.readLine());
			Pos tar = new Pos(Integer.parseInt(st.nextToken()),
					Integer.parseInt(st.nextToken()));
			
			
			Queue<Pos> q= new LinkedList<Pos>();
			
			q.add(new Pos(cur.x,cur.y));
			
			while(!q.isEmpty()) {
				Pos pos = q.poll();
				
				if(pos.x == tar.x && pos.y == tar.y) {
					break;
				}
				
				for (int i = 0; i < 8; i++) {
					
					int nx = pos.x+dx[i];
					int ny = pos.y+dy[i];
					
					//범위체크
					if(nx<0 || nx >=L || ny <0 || ny >=L)
						continue;
					//방문여부 확인
					if(visit[nx][ny]>0)
						continue;
					
					
					visit[nx][ny] = visit[pos.x][pos.y]+1;
					q.add(new Pos(nx,ny));
				}
			}
			
			System.out.println(visit[tar.x][tar.y]);
		}
	}

	static class Pos {
		int x;
		int y;

		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}