백준 7562 풀이

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

체스판에서 나이트가 이동할 수 있는 영역의 경우의 수를 찾는 문제인 것 같다.

문제의 접근방식에 대해 이제 나름 경험이 쌓였는지 이번 문제는 쉽게 파악할 수 있었다.

체스판은 2차원배열과 같고 체스말이 이동하는 것은 그 인덱스에 방문한 것과 같기 때문에 그래프를 탐색하는 방식으로 풀이하면 되겠다.

그래프 탐색으로 결정되었다면 dfs 혹은 bfs 인데 문제에서 dfs로는 풀이하기엔 쉽지 않아보였고(Stack의 문제) bfs로 풀기로 했다.

기본적인 흐름은 방문한 위치를 기록하고 좌표를 큐에 저장하여 목적지에 도착하면 끝내면 된다.

자바에서는 pair 클래스 라이브러리가 없기때문에 pair 클래스를 정의해야 했고 특히 pair의 유형이 2종류라 pair 클래스를 2개 작성해야 했다.

제네릭으로 처리할 수 있을 줄 알았는데 이 부분이 미숙해 제대로 처리하지 못해 조금 불편하게 코드를 작성한것 같다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int count = 0;
    static int index = 0;
    static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
    static int[] dy = {1, -1, 2, -2, 2, -2, 1, -1};
    static boolean visit[][];
    static int n, m;
    static int graph[][];
    static Pair end;
    static Queue<Pair2> queue;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String tc = br.readLine();
        int t = Integer.parseInt(tc);
        for (int it = 0; it < t; it++) {
            count = 0;
            String num = br.readLine();
            n = Integer.parseInt(num);
            graph = new int[n][n];
            visit = new boolean[n][n];
            for (int h = 0; h < n; h++) {
                for (int j = 0; j < n; j++) {
                    visit[h][j] = false;
                }
            }
            String l1 = br.readLine();
            String[] start = l1.split(" ");
            Pair p = new Pair(Integer.parseInt(start[0]), Integer.parseInt(start[1]));
            String l2 = br.readLine();
            String[] dest = l2.split(" ");
            end = new Pair(Integer.parseInt(dest[0]), Integer.parseInt(dest[1]));
            queue = new LinkedList<>();
            Pair2 pair = new Pair2(0, p);
            queue.offer(pair);
            while(!queue.isEmpty()){
                Pair2 tmp = queue.poll();
                int x = tmp.pair.x;
                int y = tmp.pair.y;
                visit[x][y] =true;
                int cnt = tmp.cnt;
                //System.out.println(x+","+y);
                if(x == end.x && y == end.y) {
                    //System.out.println("fin");
                    count = tmp.cnt;
                    break;
                }
                for (int i = 0; i < 8; i++) {
                    if ((x + dx[i] >= 0 && x + dx[i] <= n - 1) && (y + dy[i] >= 0 && y + dy[i] <= n - 1)) {
                        if(!visit[x+dx[i]][y+dy[i]]) {
                            visit[x+dx[i]][y+dy[i]] = true;
                            //System.out.println((x+dx[i])+","+(y+dy[i]));
                            Pair pa = new Pair(x + dx[i], y + dy[i]);
                            queue.offer(new Pair2(cnt + 1, pa));
                        }
                    }
                }
            }
            bw.write(Integer.toString(count) + "\n");
        }

        br.close();
        bw.close();
    }
}

class Pair {
    public int x;
    public int y;

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

class Pair2 {
    public int cnt;
    public Pair pair;

    public Pair2(int cnt, Pair pair){
        this.cnt = cnt;
        this.pair = pair;
    }
}