[BOJ/백준] 나이트의 이동 (bfs)

백준 7562: 나이트의 이동
- 풀이 핵심
- 정답 코드 (BFS)
마무리

알고리즘 능력을 회복하기 위해 알고리즘 종류 별로 하루에 2~3개씩 풀어가려고합니다. 한 번 걸었던 길을 다시 걷는 길이라 회복하는데 오랜 시간이 걸릴 거라고 생각하지 않습니다.

이번 문제는 알고리즘의 기본 스킬 중에 기본이라고 할 수 있는 넓이 우선 탐색(bfs)을 활용한 문제 풀이를 하려고합니다.

백준 7562: 나이트의 이동

문제의 내용은 간단합니다. 체스판 위에는 나이트 1개가 놓여져 있고, 시작점에서 끝점으로 이동할 때, 최소한의 횟수는 얼마인지 찾는 문제입니다.

주의할 점은 일반적으로 상하좌우로 이동하는 반면, 이 문제의 경우는 (2,1), (1,2)와 같이 대각선으로 이동할 수 있습니다.

풀이 핵심

문제를 보고 탐색 문제라고 판단했다면, 무엇을 구하는지에 따라 dfs를 사용할 것인지 bfs를 사용할 것인지 결정해야합니다. 이 문제의 풀이 핵심은 최소 이동 횟수를 구하라는 것입니다. 일반적으로 dfs는 전체를 탐색해야하는 경우 사용하고, 최단 경로를 탐색하기 위해서는 bfs를 사용하게 됩니다.

따라서 이번 문제는 BFS를 사용해서 풀어야 함을 알 수 있습니다. 지금 부터 풀이 방법을 소개해보도록 하겠습니다.

정답 코드 (BFS)

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

public class Boj7562 {
    private static int n; // 테스트 케이스 개수
    private static int l; // 체스판 길이
    private static int[] dx = {-1, -2, -1, -2, 1, 2, 1, 2}; // x 이동 방향
    private static int[] dy = {-2, -1, 2, 1, -2, -1, 2, 1}; // y 이동 방향

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        String[] ins;

        while (n-- != 0) {
            l = Integer.parseInt(br.readLine());
            ins = br.readLine().split(" ");
            Point start = new Point(Integer.parseInt(ins[0]), Integer.parseInt(ins[1]), 0);

            ins = br.readLine().split(" ");
            Point end = new Point(Integer.parseInt(ins[0]), Integer.parseInt(ins[1]), 0);
            bw.write(bfs(start, end) + "\n");
            bw.flush();
        }

        bw.close();
    }

    public static int bfs (Point start, Point end) {
        // BFS를 위한 큐 생성
        Queue<Point> q = new LinkedList<>();
        
        // 방문된 곳을 체크하기 위한 배열
        boolean[][] visited = new boolean[301][301];

        // 큐에 시작점 삽입
        q.offer(start);
        int min = Integer.MAX_VALUE;

        while (!q.isEmpty()) {
            Point curPos = q.poll();  // 현재 위치 조회

            // 끝지점에 도착한 경우, 지금까지 이동한 횟수와 지금까지의 최솟값을 비교해 업데이트
            if (curPos.x == end.x && curPos.y == end.y) {
                min = Math.min(min, curPos.c);
            }

            for (int i = 0; i < 8; i++) {
                // 다음 지점 설정
                int nx = curPos.x + dx[i];
                int ny = curPos.y + dy[i];
                if (nx < 0 || nx > l - 1 || ny < 0 || ny > l - 1) {
                    continue;
                }

                // 다음 지점이 방문한 곳이 아니라면 새위치로 이동하면서 이동 횟수 + 1로 설정
                // 다음 지점은 방문할 예정이기 때문에 true로 설정
                if (!visited[nx][ny]) {
                    q.offer(new Point(nx, ny, curPos.c + 1));
                    visited[nx][ny] = true;
                }
            }
        }

        // 최소값 리턴
        return min;
    }

    private static class Point {
        int x;  // x 위치
        int y;  // y 위치
        int c;  // 이동 횟수
        Point (int x, int y, int c) {
            this.x = x;
            this.y = y;
            this.c = c;
        }
    }
}

마무리

일반적으로 코딩 테스트에서 쉬운 난이도로 자주 나오는 형태로 풀이 방법을 꼭 익혀서 손쉽게 문제를 풀 수 있었으면 좋겠습니다. 혹시 궁금하신 점이나 이상한 점이 있다면 댓글 부탁드리겠습니다.

감사합니다.

#나이트 이동,
#능력 회복하기,
#백준,
#백준 7562,
#알고리즘

글이 도움이 되셨다면, 커피 한 잔만 사주세요!

Comments

Copied to clipboard

[BOJ/백준] 나이트의 이동 (bfs)

Table of Contents

백준 7562: 나이트의 이동

풀이 핵심

정답 코드 (BFS)

마무리