★백준/7562 나이트의 이동 /bfs

나이트의 이동 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

44259

22440

16709

49.655%

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1 복사

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1 복사

5
28
0

 

---

풀이

bfs 최소이동문제
체스판의 범위를 넘는지 체크해줘야하고, 최소 이동이므로 이미 방문했던 위치는 큐에 넣지않는다.
나이트가 이동하는 규칙은 따로 배열로 저장해서 사용한다.

bfs 최소이동문제 구현의 두가지방법
1. boolean 방문배열을 이용하여 방문체크하고 , 큐에는 이동하는 횟수를 같이 전달해줘서 , 목적지 도착하면 이동한 횟수를 출력하는 방법.
2. boolean 방문배열과 각 좌표에 이동횟수를 저장할 map 또는 result 배열을 이용하여 , bfs 돌고 난후 목적지 좌표에 저장된 값을 출력하는 방법.

 

1번 BFS -> 방문배열사용, 큐에 이동하는횟수 같이 전달해서 목적지 좌표 도착시 이동횟수 출력

 

 static void solve() throws IOException {
        for (int t = 0; t < testcase; t++) {
            n = Integer.parseInt(br.readLine());
//            result = new int[n][n];
            visited = new boolean[n][n];
            startPosition = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                .toArray();
            targetPosition = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                .toArray();
            bfs();
        }


    }

    static void bfs() throws IOException {
        Queue<int[]> q = new LinkedList<>();
        int startX = startPosition[0];
        int startY = startPosition[1];
        visited[startX][startY] = true;
        q.add(new int[]{startX, startY, 0});

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int currentX = current[0];
            int currentY = current[1];
            int currentMove = current[2];
            if (currentX == targetPosition[0] && currentY == targetPosition[1]) {
                bw.write(currentMove+"\n");
                break;
            }

            for (int i = 0; i < 8; i++) {
                int nextX = currentX + di[i];
                int nextY = currentY + dj[i];

                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n) {
                    if (!visited[nextX][nextY]) {
                        visited[nextX][nextY] = true;
                        q.add(new int[]{nextX, nextY,currentMove+1});
                    }
                }
            }


        }



    }

 

 

 

2번 Bfs -> 방문배열을 사용하고, 각 좌표에 최소이동횟수가 저장되는 배열을 사용한다.  bfs를 다돌고 나면(갈수있는곳의 좌표에 이동횟수를 다 채우고나면)  목표지의 좌표를 출력한다.

static int testcase,n;
static int[][] moveMap;
static boolean[][] visited;
static int[] startPosition;
static int[] targetPosition;

static final int[] di = {1, 2, 2, 1, -1, -2, -2, -1};
static final int[] dj = {2, 1, -1, -2, 2, 1, -1, -2};
public static void main(String[] args) throws IOException {

    input();
    solve();

    bw.flush();
    bw.close();

}

static void input() throws IOException {
    testcase = Integer.parseInt(br.readLine());
}

static void solve() throws IOException {
    for (int t = 0; t < testcase; t++) {
        n = Integer.parseInt(br.readLine());
        moveMap = new int[n][n];
        visited = new boolean[n][n];
        startPosition = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
            .toArray();
        targetPosition = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
            .toArray();
        bfs();
        bw.write(moveMap[targetPosition[0]][targetPosition[1]]+"\n");
    }


}

static void bfs() throws IOException {
    Queue<int[]> q = new LinkedList<>();
    int startX = startPosition[0];
    int startY = startPosition[1];
    visited[startX][startY] = true;
    q.add(startPosition);

    while (!q.isEmpty()) {
        int[] current = q.poll();
        int currentX = current[0];
        int currentY = current[1];

        for (int i = 0; i < 8; i++) {
            int nextX = currentX + di[i];
            int nextY = currentY + dj[i];

            if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n) {
                if (!visited[nextX][nextY]) {
                    visited[nextX][nextY] = true;
                    moveMap[nextX][nextY] = moveMap[currentX][currentY] + 1;
                    q.add(new int[]{nextX, nextY});
                }
            }
        }


    }



}

 

3. 메모리초과  큐에서 꺼낼때 방문처리

    static void bfs() throws IOException {
        Queue<int[]> q = new LinkedList<>();
        int startX = startPosition[0];
        int startY = startPosition[1];
        visited[startX][startY] = true;
        q.add(startPosition);

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int currentX = current[0];
            int currentY = current[1];
            visited[currentX][currentY] = true;

            for (int i = 0; i < 8; i++) {
                int nextX = currentX + di[i];
                int nextY = currentY + dj[i];

                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n) {
                    if (!visited[nextX][nextY]) {
                        moveMap[nextX][nextY] = moveMap[currentX][currentY] + 1;
                        q.add(new int[]{nextX, nextY});
                    }
                }
            }


        }



    }

 

결론

모든경우를 다돌아보는 2번 방법이 아주 조금 더 오래걸렸다.