[백준 7562] 나이트의 이동

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

---

• 문제설명
  먼저 첫 번째 줄에 테스트 케이스의 개수를 입력받고 이 테스트 케이스만큼 차례대로 체스판의 크기, 나이트가 현재 있는 칸의 좌표, 나이트가 이동하려는 칸의 좌표를 입력받는다.
  각 테스트 케이스마다 나이트가 최소 몇번만에 현재 칸에서 목표 칸 까지 이동하는지 구하면 된다.

• 제출코드     

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

public class Main {
    static int l;
    static int start_x, start_y, end_x, end_y;

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

    static int [][] visited;
    static int [][] map;

    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int [] {start_x, start_y});
        visited[start_x][start_y] = 1;

        while (!q.isEmpty()){
            int [] cur = q.poll();
            int x = cur[0];
            int y = cur[1];

            for(int i = 0; i < dx.length; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx >= 0 && ny >= 0 && nx < l && ny < l){
                    if(visited[nx][ny] == 0){
                        q.add(new int[] {nx, ny});
                        map[nx][ny] = map[x][y] + 1;
                        visited[nx][ny] = 1;
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            l = Integer.parseInt(br.readLine());

            visited = new int[l][l];
            map = new int[l][l];

            StringTokenizer st = new StringTokenizer(br.readLine());

            start_x = Integer.parseInt(st.nextToken());
            start_y = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());

            end_x = Integer.parseInt(st.nextToken());
            end_y = Integer.parseInt(st.nextToken());

            bfs();

            sb.append(map[end_x][end_y]).append("\n");
        }

        System.out.println(sb);
    }

}

 

• 코드설명
  먼저 문제에서 '최소'라는 키워드가 나왔으므로 이는 BFS를 이용해서 문제를 풀면 된다.
  일단 나이트가 이동할 수 있는 방향을 dx, dy배열에 저장해두었다.
  주어진 나이트의 시작 좌표를 큐에 넣고 큐가 빌 때까지 탐색을 시작한다.
  큐에서 하나씩 꺼내서 for문을 통해 8방향 모두 체크해 준다. 몇 번 이동했는지는 map배열에 1씩 더해 나가고, visited배열을 통해 방문 여부를 확인한다.
  
  

---

• 마무리
  먼저 이 문제를 풀기 위해서는 bfs의 개념을 알아야 한다.

BFS 짜는 법

BFS는 보통 큐를 이용한 방식을 사용한다.
큐의 가장 앞에 있는 노드를 불러서 다음노드들을 맨 뒤에 놓으면,
결국 먼저 왔던 노드들은 먼저 처리되고 나중에 불러진 노드들은 나중에 처리된다.
BFS는 이런 특징을 이용해서, 같은 거리에 있는 어떤 지점을 처리한 뒤에 다음 거리에 있는 지점을 탐색할 수 있기 때문에 최단거리로 쓸 수 있는 것이다.

BFS에서 가장 중요한 것은 무엇일까!? 바로, 방문 체크를 잘 만들어야 한다는 것이다!
방문 체크를 잘 못 만들면 큐에 들어갔던 값이 또 들어가고.. 또 들어가고... 또 들어가서 메모리가 터져버린다...

struct COD{int r, c};
 
queue<COD> que;
 
while(!que.empty()){
    COD now = que.front();
    que.pop();
 
    //now를 이용한 적절한 처리
    ...
 
    for(/*다음에 올 노드들 보기*/){
        COD next;
 
        //다음 노드로 올 수 있는 적절한 노드인지 확인합니다.
        //방문에 대한 처리, 인덱스가 주어진 문제 밖으로 나갔는지에 대한 처리 등이 포함됩니다.
        if(...){
            //방문 처리를 합니다.
            ...
            que.push(next);
        }         
    }
}​

큐가 빌 때까지 처리하고, 현재 노드에서 다음 노드가 어떻게 되는지 반복문을 통해 처리한다.
그리고, next가 유효하다면 큐에 다음 노드를 넣는 방식이다!


이제, 문제의 목표에 따라서 프로그래밍을 하는 방법을 살펴보겠다.

1. 딱 하나의 목표에 최단 거리로 도착하는 경우!
2. 여러 개의 목표 중 하나에 최단 거리로 도착해서, 해당 지점들에 대해서 적절한 처리를 해야 하는 경우!

목표가 하나일 경우에는 찾자마자 바로 return을 해주면 된다.

struct COD{int r, c};
 
queue<COD> que;
 
while(!que.empty()){
    COD now = que.front();
    que.pop();
    
    //now를 이용한 적절한 처리를 합니다.
    ...

    //now가 목표라면
    if(...){
        //목표에 대한 처리 후 반복문을 빠져나옵니다.
        ...
        break;
    }
 
    for(/*다음에 올 노드들 보기*/){
        COD next;
 
        //다음 노드로 올 수 있는 적절한 노드인지 확인합니다.
        //방문에 대한 처리, 인덱스가 주어진 문제 밖으로 나갔는지에 대한 처리 등이 포함됩니다.
        if(...){
            //방문 처리를 합니다.
            ...
            que.push(next);
        }         
    }
}​

하지만, 목표가 여러 개라면 아직 처리 못한 목표가 큐에 남아있을 수 있다.
결국엔 현재 거리를 기억해서, 큐에서 현재 거리와 같은 거리를 가지는 노드들을 처리할 때까지 반복문을 진행하는 것이 필요하다.
여러 방법이 있지만, 현재 거리에 대한 노드가 몇 개 있는지를 먼저 저장하는 방식을 보겠다.

struct COD{int r, c};
 
queue<COD> que;
 
//초기 세팅
COD first = ...
 
//first 방문 체크
...
que.push(first);
 
while(que.size()){
    int cnt = que.size();
 
    //노드가 목적지에 도달했는지에 대한 변수
    bool isend = false;
 
    while(cnt--){
        COD now = que.front();
        que.pop();
 
        //now에 대한 처리를 합니다.
        ...
 
        //now가 최종 목적지일 경우 처리후 다음 노드로 넘어갑니다.
        if(...){
            isend = true;
            continue;
        }
 
        //다음 노드들 탐색
        for(...){
            //다음 노드에 대한 처리
            COD next = ...
 
            //다음 노드로 올 수 있는 적절한 노드인지 확인합니다.        
            //방문에 대한 처리, 인덱스가 주어진 문제 밖으로 나갔는지에 대한 처리 등이 포함됩니다.            
            if(...){
                //방문 처리를 합니다.
                ...
 
                que.push(next);
            }
        }
        
    }
    
    //목적지에 도달했으면 반복문을 빠져나옵니다.
    if(isend) break;
    //현재 거리에 대한 처리 후 다음에 대한 처리를 위한 처리를 합니다.
    ...     
 
}​