[실버1] 7562. 나이트의 이동 (Java)

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

7562번: 나이트의 이동

왤케 체스를 좋아해,,

---

※  문제를 요약하면 아래와 같습니다.

▶ NxN 체스판에서 어떤 나이트의 현재 위치와 목표 위치가 주어 졌을 때, 최소로 움직여 도달할 수 있는 횟수 구하기

▶  Input : 첫째 줄엔 테스트 케이스 경우 입력, 각 테스트 별 첫째 줄엔 N, 다음 줄에 현재 위치, 다음 줄에 목표 위치 입력

                 ( 위치는 (Row, Col)의 0 부터 시작하는 좌표값 )

▶  Output : 각 테스트 케이스 별로 나이트가 최소 몇 번만에 이동할 수 있는지 출력

---

◈ Input - 1

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

◈ Output - 1

5
28
0

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 최소 횟수 탐색 == BFS

▶ 방문 처리 필수

▶ BFS에서 델타 탐색을 상,하,좌,우 가아닌 실제 체스에서 말이 이동 가능한 경로를 탐색 (가로2 세로1 or 가로1 세로2)

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Point {
	int m_nRow;
	int m_nCol;
	int m_nCount;

	public Point(int m_nRow, int m_nCol, int m_nCount) {
		super();
		this.m_nRow = m_nRow;
		this.m_nCol = m_nCol;
		this.m_nCount = m_nCount;
	}

}

public class Main {

	static boolean[][] barrVisited;
	static int N, nStartRow, nStartCol, nEndRow, nEndCol, nResult;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(bReader.readLine());

		for (int i = 0; i < T; i++) {
			N = Integer.parseInt(bReader.readLine());

			// 맵 크기 설정 하자
			barrVisited = new boolean[N][N];

			StringTokenizer st = new StringTokenizer(bReader.readLine());
			nStartRow = Integer.parseInt(st.nextToken());
			nStartCol = Integer.parseInt(st.nextToken());

			st = new StringTokenizer(bReader.readLine());
			nEndRow = Integer.parseInt(st.nextToken());
			nEndCol = Integer.parseInt(st.nextToken());

			nResult = 0;
			BFS();
			bWriter.write(String.valueOf(nResult) + '\n');
			bWriter.flush();
		}

		
		bWriter.close();

	}

	private static void BFS() {
		Queue<Point> queueBFS = new LinkedList<>();

		queueBFS.add(new Point(nStartRow, nStartCol, 0));

		// 나이트 움직임 만큼 가자
		// 북동 부터 북서로 시계방향
		int[] dr = { 2, 1, -1, -2, -2, -1, 1, 2 };
		int[] dc = { 1, 2, 2, 1, -1, -2, -2, -1 };

		while (!queueBFS.isEmpty()) {
			Point p = queueBFS.poll();
	
			if(p.m_nRow == nEndRow && p.m_nCol == nEndCol) {
				nResult = p.m_nCount;
				queueBFS.clear();
				break;
			}
			
			if(barrVisited[p.m_nRow][p.m_nCol])
				continue;
			
			barrVisited[p.m_nRow][p.m_nCol] = true;
			
			for(int i = 0; i < dr.length; i++) {
				int nSearchRow = p.m_nRow + dr[i];
				int nSearchCol = p.m_nCol + dc[i];
				
				// 범위 벗어나거나 방문했으면 나가버려
				if(nSearchRow < 0 || nSearchCol < 0 || nSearchRow >= N || nSearchCol >= N
						|| barrVisited[nSearchRow][nSearchCol])
					continue;

				queueBFS.add(new Point(nSearchRow, nSearchCol, p.m_nCount+1));
			}
			
		}
	}

}

---

Good Luck! (피드백 감사합니다!)