백준 - 7562번, 나이트의 이동(sol.java)

◎문제 링크

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

7562번: 나이트의 이동

---

◎문제 파악

기본적인 bfs문제이다. 움직이는 주체가 나이트라서 상하좌우로만 움직였던 다른 bfs문제와는 다르게 역동적으로 움직인다.

 

나이트의 움직임

출처: https://www.pinterest.co.kr/pin/379991287294948019/

체스의 나이트는 위의 그림과 같이 움직인다.

현재 나이트의 위치에서

index	x	y
1	-1	-2
2	-2	-1
3	-2	+1
4	-1	+2
5	+1	+2
6	+2	+1
7	+2	-1
8	+1	-2

이렇게 8개의 방향으로 움직인다.

또한, 유명한 문제인 나이트의 여행  에서 우리가 알고 있듯이, 정사각형인 체스판에서 나이트는 어디든지 갈 수 있다. 그러므로, 보드판의 어떤 좌표가 주어지든간에 나이트가 갈 수 있는 위치이다.

---

◎코드 구현

package project;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main{
    int boardLength; //보드판 한 변의 길이
    int[][] board; //보드판 이차원 배열
    coordinate start; //시작 좌표
    coordinate goal; //끝 좌표
    Queue<coordinate> q = new LinkedList<coordinate>();//BFS용 queue 
    
    
    public static void main(String[] args) throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        for(int i = 0; i<N; i++){
            Main m = new Main();
            m.boardLength = Integer.parseInt(br.readLine());
            m.board = new int[m.boardLength][m.boardLength];
            
            String[] inputTmp = (br.readLine()).split(" ");
            m.start = 
                new coordinate(Integer.parseInt(inputTmp[0]),Integer.parseInt(inputTmp[1]));

            
            inputTmp = (br.readLine()).split(" ");
            m.goal = 
                new coordinate(Integer.parseInt(inputTmp[0]),Integer.parseInt(inputTmp[1]));
        
            if(m.start.x == m.goal.x && m.start.y == m.goal.y ){
                System.out.println(0);
            }else{
                m.q.add(m.start);
                m.bfs();
            }
        }
    }
    
    //
    public boolean isIn(int x, int y){
        if(x>=0 && x<boardLength && y>=0 && y<boardLength){
            return true;
        }else{
            return false;
        }
    }
    
    
    //bfs
    public void bfs(){
        
        //int p = 0;
        while(!q.isEmpty()){
            
            //출력
            /*
            p++;
            System.out.println(p);
            for(int i = 0; i<boardLength; i++){
                for(int j = 0; j<boardLength; j++){
                    System.out.print(board[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println();
            System.out.println();
            */
            
            
            if(board[goal.x][goal.y] != 0){
                System.out.println(board[goal.x][goal.y]);
                break;
            }
            
            coordinate now = q.poll();
            //나이트가 움직일 수 있는 경로를 모두 움직여봄
            move(now,-1,-2);
            move(now,-2,-1);
            move(now,-2,+1);
            move(now,-1,+2);
            move(now,+1,+2);
            move(now,+2,+1);
            move(now,+2,-1);
            move(now,+1,-2);            
        }
    }
    
    
    //나이트 움직이기
    public void move(coordinate c, int x, int y){
        
        //움직임이 보드안에 있으면
        if(isIn(c.x + x, c.y + y) == true){
            //처음으로 도착한 곳이면
            if(board[c.x + x][c.y + y] ==0){
                board[c.x + x][c.y + y] = board[c.x][c.y] + 1;
                q.add(new coordinate(c.x + x, c.y + y ));
            }
            
        }
    }
        
}
    


class coordinate{
    int x; //x 좌표
    int y; //y 좌표
    coordinate(int x, int y){
        this.x = x;
        this.y =y;
    }
}

나이트의 이동횟수 값을 보드판(이차원 배열)에 적어주며 BFS를 실행하였다.

---

백준 BFS문제 풀이 중에 스스로 가장 깔끔하게 풀이한 문제이다. 난이도가 쉽기도 했지만, 같은 유형의 여러 문제를 풀다보면 코드가 간결해지는 게 느껴져서 신기하다.