57 삐약 : 백준 7562| 나이트의 이동 [바킹독 문제 풀이|BFS|JAVA]

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

 

package BKD_0x9_BFS;

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

public class BOJ_7562 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

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


        while(T-->0){
            int I = Integer.parseInt(br.readLine());
            int[][] dist = new int[I][I];
            int[][] visited = new int[I][I];

            StringTokenizer st = new StringTokenizer(br.readLine());
            int st_x= Integer.parseInt(st.nextToken());
            int st_y = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int dst_x= Integer.parseInt(st.nextToken());
            int dst_y = Integer.parseInt(st.nextToken());


            Queue<Pair> q= new LinkedList<Pair>();
            q.offer(new Pair(st_x, st_y));
            dist[st_x][st_y] =0;
            visited[st_x][st_y]=1;

            for(int i=0;i<I;i++){
                for(int j=0;j<I;j++){
                    while(!q.isEmpty()){
                        Pair p = q.poll();

                        if(p.x==dst_x && p.y == dst_y){
                            System.out.println(dist[p.x][p.y]);
                            break;
                        }

                        for(int k=0;k<8;k++){
                            int nx = p.x+dx[k];
                            int ny = p.y+dy[k];

                            if(nx>=0 && nx<I &&ny>=0 && ny<I && visited[nx][ny]==0){
                                visited[nx][ny] =1;
                                dist[nx][ny] = dist[p.x][p.y] +1;
                                q.offer(new Pair(nx,ny));

                            }
                        }
                    }
                }
            }
        }
    }
    public static class Pair{
        int x;
        int y;

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

 

방향을 탐색하기 위해 선언하는 변순인 dx, dy 배열을 나이트의 움직임에 맞게 조정을 한 뒤 보편적인 bfs문제처럼 풀면 해결된다

이제 좀 bfs에 대한 감을 잡아가는 것 같아서 아주 뿌듯하다.

 

아.

 

그리고

 

본인.

 

데이식스 5th 팬미팅 갑니다.

 

그냥 자랑하고 싶었음

 

꺄륵