[TIL] 99클럽 코테 스터디 9일차 TIL + 백준 7562 나이트의 이동

 

문제 풀이

문제 탐색하기

BFS 알고리즘을 활용하여 풀이 설계하기

 

너비 우선 탐색(BFS, Breadth-First Search) 이란?

그래프 탐색 알고리즘으로, 너비를 우선으로 하여 탐색을 진행합니다. 시작 노드에서 가까운 노드를 우선적으로 탐색하며, 동일 레벨에 있는 노드를 모두 탐색한 후 다음 레벨로 넘어가는 방식입니다. BFS는 일반적으로 큐(Queue) 자료 구조를 사용하여 구현합니다.

 

BFS알고리즘에 대한 기본적인 개념 설명하고 관련 문제는 아래의 게시글에 자세히 나와있습니다.

https://coding-babo.tistory.com/152

[TIL] 99클럽 코테 스터디 5일차 TIL + 백준 24444 너비 우선 탐색 1

 

 

이 문제에서 중요한 점은 나이트가 이동하는 패턴을 어떻게 활용할 것인가 입니다.

나이트는 가로1세로2 또는 가로2세로1 패턴으로 움직일 수 있습니다. 따라서 움직일 수 있는 패턴을 배열에 넣어둔 상태로 bfs 탐색을 진행하면 됩니다.

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

 

queue에 방문한 체스판의 위치를 하나씩 저장하고 빼면서 체스판의 규격에 맞는 위치 내에서 탐색을 반복합니다.

탐색하다가 목적지로 도착했을 경우 종료하면 됩니다.

 

문제 풀이

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 Main {

    static int I;
    static int[][] chess;
    static boolean[][] visited;
    static int nowX, nowY;
    static int desX, desY;
    static int[][] pos = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

    private static void bfs(int x, int y){
        Queue<int[]> queue = new LinkedList();
        queue.add(new int[]{x, y});

        while(!queue.isEmpty()){
            int[] now = queue.poll();
            int nowX = now[0];
            int nowY = now[1];

            for(int i=0; i<pos.length; i++){
                int nX = nowX + pos[i][0];
                int nY = nowY + pos[i][1];

                if(nX < 0 || nX >= I || nY < 0 || nY >= I || visited[nX][nY] || chess[nX][nY] != 0){
                    continue;
                }

                chess[nX][nY] = chess[nowX][nowY] + 1;
                visited[nX][nY] = true;
                queue.add(new int[]{nX, nY});
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());


        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for(int i=0; i<N; i++){
            I = Integer.parseInt(br.readLine());
            chess = new int[I][I];
            visited = new boolean[I][I];

            st = new StringTokenizer(br.readLine());
            nowX = Integer.parseInt(st.nextToken());
            nowY = Integer.parseInt(st.nextToken());

            visited[nowX][nowY] = true;

            st = new StringTokenizer(br.readLine());
            desX = Integer.parseInt(st.nextToken());
            desY = Integer.parseInt(st.nextToken());

            bfs(nowX, nowY);
            sb.append(chess[desX][desY]).append("\n");
        }

        System.out.println(sb.toString());
    }
}

 

오늘의 회고

BFS알고리즘으로 풀면 되지 않을까 생각했지만 맘처럼 쉽게 풀리지 않았습니다.. 좋은 풀이법을 제공해주시는 구글의 많은 개발자분들의 도움을 받아서 문제를 풀 수 있었습니다. 같은 문제라도 여러번 풀면서 감을 익히는 것도 중요할 것 같네여...