[JAVA]BOJ(백준) - 나이트의 이동 - 7562

문제 내용

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

7562번: 나이트의 이동

 

기존에 풀던 BFS 문제인데 단지 방향을 나타내는 배열만 바뀌었을뿐..

---

문제 접근 방법

지금까지 상하좌우만 판단하던 문제에서 상하좌우가 8가지 방향(나이트 이동방향)으로 이동하면서 목표점까지 몇번 이동했는지 체크하면 되는 문제이다.

 

말의 이동방향을 나타내는 배열은

y축으로 +2 일때 x축으로 +1,-1

y축으로 -2 일때 x축으로 +1,-1

x축으로 +2 일때 y축으로 +1,-1

x축으로 -2 일때 y축으로 +1,-1

 

이렇게 8가지 방향을 체크해줄수 있는 배열을 만들면된다.

 

그리고 나는 boolean으로 방문 배열을 따로 만들었지만, 이 문제에선 map배열로 이동횟수 체크와 동시에 방문여부(0이거나 아니거나)도 확인 할수 있기때문에 그냥 map배열만 써도 문제없어 보인다.

---

 

풀이

package org.boj.dfs.bfs;

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

class Point7562{
	int pointX;
	int pointY;
	
	public Point7562(int v1, int v2) {
		this.pointX = v1;
		this.pointY = v2;
	}
}

public class BOJ_7562 {
	static int T, I; //테케, 체스판크기
	static boolean[][] check; //방문 배열
	static int[][] night = new int[2][2]; //시작점([0][0],[0][1])과 끝점([1][0],[1][1])
	static int[][] map; //몇번 이동하는지 담을 배열
	static ArrayList<Integer> list = new ArrayList<Integer>(); //횟수담을 리스트
	
	static int[] x = {2, 2, -2, -2, 1, -1, 1, -1}; //나이트 이동방향
	static int[] y = {1, -1, 1, -1, 2, 2, -2, -2}; //나이트 이동방향
	
	public void bfs(int v1, int v2) {
		Queue<Point7562> queue = new LinkedList<Point7562>();
		queue.add(new Point7562(v1, v2));
		check[v1][v2]=true; //첫점 방문처리
		
		while(!queue.isEmpty()) {
			Point7562 point = queue.poll();
			
			//지금뽑은 객체의 점이 목표점과 같으면 이동 끝났다고 보면됨.
			if(point.pointX == night[1][0] && point.pointY == night[1][1]) {
				list.add(map[point.pointX][point.pointY]);
				return;
			}
			
			for(int i=0; i<8; i++) {
				int dx = point.pointX + x[i];
				int dy = point.pointY + y[i];
				
				
				if(dx>=0 && dy>=0 && dx<I && dy<I) {
					if(!check[dx][dy]) {
						check[dx][dy]=true;//방문 처리
						map[dx][dy]=map[point.pointX][point.pointY]+1;//횟수 증가
						queue.add(new Point7562(dx, dy));
					}
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {
			I = Integer.parseInt(br.readLine());
			check = new boolean[I][I];
			map = new int[I][I];
			for(int j=0; j<2; j++) {
				st = new StringTokenizer(br.readLine());
				for(int k=0; k<2; k++) {
					night[j][k] = Integer.parseInt(st.nextToken());
				}
			}
			new BOJ_7562().bfs(night[0][0],night[0][1]);
		}
		
		//출력
		for(int a:list) {
			System.out.println(a);
		}
	}
}

 

---

마치며

기존에 풀었던 BFS문제에서 나이트의 이동방향만 잘 체크해주면 되는 문제라 크게 어려운 문제는 아니였다.