[BAEKJOON 백준] 7562 나이트의 이동

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

LinkedList를 이용을 해서 문제를 해결했다.

 

그리고 나이트가 움직일 수 있는 8가지 방향을 배열로 만들어 주고, Point 클래스를 이용을 해서 계산을 했다.

 

그리고 visit 배열을 이용을 해서 나이트가 한번 방문한 곳은 다시 방문하지 않도록 했다.

 

시작점과 도착점을 가지고, 나이트가 해당 도착점에 도착할 경우 while 문에서 나오도록 했다.

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	static class Point {
		int x, y;

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

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

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		for (int t = 1; t <= T; t++) {
			LinkedList<Point> que = new LinkedList<>();
			int N = sc.nextInt();
			boolean visit[][]=new boolean[N][N];
			int x=sc.nextInt();
			int y=sc.nextInt();
			que.offer(new Point(x, y));	//시작점
			visit[x][y]=true;
			int result=0;
			Point last = new Point(sc.nextInt(), sc.nextInt());	//도착점
			outer:
			while(!que.isEmpty()) {
				int size=que.size();
				for(int i=0;i<size;i++) {
					Point temp=que.poll();
					if(temp.x==last.x&&temp.y==last.y) {	//도착점에 도착하면 while문을 끝낸다.
						break outer;
					}
					for(int k=0;k<8;k++) {	// 나이트가 이동할 수 있는 모든 곳을 확인한다.
						int xx=temp.x+dx[k];
						int yy=temp.y+dy[k];
						if(xx>=0&&xx<N&&yy>=0&&yy<N&&!visit[xx][yy]) {	//가능하면 리스트에 넣는다.
							que.offer(new Point(xx,yy));
							visit[xx][yy]=true;
						}

					}
				}
				result++;
			}
			System.out.println(result);

		}

	}

}