백준 7562 - 나이트의 이동

Java

7562 번 - 나이트의 이동

문제

접근 방법

처음 방문하는 것이 가장 적은 횟수로 도달하는 BFS의 성질을 통해 해결하였다.

BFS의 queue에는 {y, x, 그리고 cnt(현재까지 도달하는데 걸린 횟수)}를 담는다.

이후 Knight가 갈 수 있는 8가지 방향을 한번씩 옮겨보며 문제에서 주어진 좌표로 갈 때 까지 반복한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result, tc;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	tc = stoi(br.readLine());

    	while(tc-- != 0) {
    		n = stoi(br.readLine());
    		boolean[][] map = new boolean[n][n];

    		int sy, sx, ey, ex;
    		stk = new StringTokenizer(br.readLine());	//  시작 점
    		sy = stoi(stk.nextToken());
    		sx = stoi(stk.nextToken());

    		stk = new StringTokenizer(br.readLine());	// 도착 점
    		ey = stoi(stk.nextToken());
    		ex = stoi(stk.nextToken());

    		Queue<int[]> queue = new LinkedList<int[]>();
    		int[] q;
    		int y,x, ny,nx, cnt;

    		int[] dy = {-2,-1,1,2,2,1,-1,-2};	// Knight의 이동 방향
    		int[] dx = {1,2,2,1,-1,-2,-2,-1};

    		queue.add(new int[] {sy,sx,0});
    		map[sy][sx] = true;

    		while(!queue.isEmpty()) {
    			q = queue.poll();
    			y = q[0];
    			x = q[1];
    			cnt = q[2];

    			if(y == ey && x == ex) {		// 문제에서 주어진 위치
    				System.out.println(cnt);
    				break;
    			}

    			for(int i = 0; i < 8; i++) {	// 8방향으로 이동
    				ny = y + dy[i];
    				nx = x + dx[i];

    				if(isIn(ny,nx) && !map[ny][nx]) {
    					queue.add(new int[] {ny,nx,cnt + 1});
    					map[ny][nx] = true;
    				}
    			}
    		}
    	}

    	br.close();
	}

	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= n)
            return false;
        return true;
    }

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

BFS : 최소 횟수 방문

개선할 점