7562번

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

7562번: 나이트의 이동

이번 문제는 knight의 이동 문제이다. 말그대로 체크판에서 하나의 시작점에서 도착지점으로 이동하는 최소 횟수를 구하는 것이다.

즉, 나이트가 이동하는 방향은 8방향이 있다. 그림으로 나타내면 문제의 주어진 아래의 그림과 같다.

그리고 이걸 x,y 좌표로 나타내면 아래와 같이 나타낼 수 있다.

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

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

 

그리고 이 문제는 1012, 2667번과 BFS구현 로직이 거의 똑같다.

시작지점으로부터 방문 체크를 진행하면서 내부 카운팅으로 도착지점에 도달하는 최소 횟수를 구하면 된다.

내부 카운팅은 1012번과 2667번에 설명했지만 간단하세 다시 설명하자면, BFS의 로직에서 사용할 인접리스트 저장 Queue에 들어갈 target객체를 만들어 줄 때 생성자 초기화 파라미터로 카운팅 값도 같이 전달하는 방식이다.

 

예를 들자면 아래의 target클래스가 있다고 하면(귀찮아서 접근제한 처리와 getter, setter는 구현하지 않았다.)

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

여기에 추가로 cnt 즉, 카운팅 값을 넣어준다.

class target{
    int x;
    int y;
    int cnt;

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

그러면 이 객체를 이용해서 knight의 움직임을 계산해보면

아래의 BFS로직을 이용한다.

public void bfs(int Rx, int Ry) {
    queue.add(new target(Rx,Ry,0));
    table[Rx][Ry]=1;
    while (!queue.isEmpty()){
        target tmp = queue.poll();
        if(tmp.x==Ex&&tmp.y==Ey){
            count=tmp.cnt;
            return;
        }
        for(int i=0; i<8; i++){
            int x = tmp.x+dx[i];
            int y = tmp.y+dy[i];
            if(x>=0&&y>=0&&x<node&&y<node&&table[x][y]==0){
                table[x][y]=1;
                queue.add(new target(x,y,tmp.cnt+1));
            }
        }
    }
}

방문한 곳을 1로 처리하고 방문하지 않은 곳을 0으로 하였다.

 

입력은 테스트 횟수와 체스판의 크기, 시작지점, 도착지점을 받고, 탐색하는 방식으로 구성하였다.

정답 코드는 아래와 같다. 입력부분이 더럽기는 하지만 반복문과 조건문으로 넣어주기 귀찮아서 그냥 받아왔다.

package backjoon.b7562;

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 b7562 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int caseT = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<caseT; i++){
            int node = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int Rx = Integer.parseInt(st.nextToken());
            int Ry = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            int Ex = Integer.parseInt(st.nextToken());
            int Ey = Integer.parseInt(st.nextToken());
            Graph g = new Graph(node,Ex,Ey);
            g.bfs(Rx,Ry);
            sb.append(g.count).append("\n");
        }
        System.out.println(sb);
    }
}
class Graph{
    int node;
    int[][] table;
    int Ex;
    int Ey;
    int[] dx={1, 2, 2, 1,-1,-2,-2,-1};
    int[] dy={2, 1,-1,-2,-2,-1, 1, 2};
    int count=0;
    Queue<target> queue = new LinkedList<>();
    public Graph(int node, int Ex, int Ey){
        this.node=node;
        table=new int[node][node];
        this.Ex=Ex;
        this.Ey=Ey;
    }

    public void bfs(int Rx, int Ry) {
        queue.add(new target(Rx,Ry,0));
        table[Rx][Ry]=1;
        while (!queue.isEmpty()){
            target tmp = queue.poll();
            if(tmp.x==Ex&&tmp.y==Ey){
                count=tmp.cnt;
                return;
            }
            for(int i=0; i<8; i++){
                int x = tmp.x+dx[i];
                int y = tmp.y+dy[i];
                if(x>=0&&y>=0&&x<node&&y<node&&table[x][y]==0){
                    table[x][y]=1;
                    queue.add(new target(x,y,tmp.cnt+1));
                }
            }
        }
    }
}
class target{
    int x;
    int y;
    int cnt;

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