[BOJ] 99클럽 코테 스터디 9일차 TIL : 7562-나이트의 이동-BFS

 

문제

백준 나이트의 이동  | 실버 1

#그래프 이론 #그래프 탐색 #너비 우선 탐색

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

 

문제 탐색

* 나이트가 한 번에 이동할 수 있는 칸에 따라 이동해서 목표지점에 몇번만에 갈 수 있는지

* 최소로 움직이는 경우를 고르는 것이므로 BFS로 풀 수 있음

 

 

코드 설계

1. 문제의 입력 받기 (BufferedReader, StringTokenizer)

2. x, y 변수를 담을 Point 클래스 구현

3. bfs 로직 구현

    canGo로직 구현 (움직였을 때, graph 내부에 존재하는지)

4. 예제 출력을 StringBuilder로 받아서 메모리 줄이기

 

 

시도 회차 수정 과정

1회차

* 처음에 횟수 세는 부분을 빠트려서 graph 배열을 새롭게 만들었다.

 

2회차

* canGo, isEnd 함수를 따로 빼서 코드 리팩토링 진행

 

정답 코드

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 l, s1, s2, e1, e2, cnt = 0;
    static Queue<Point> queue = new LinkedList<>();
    static int[][] graph;
    static int[][] visited;

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

        int n = Integer.parseInt(br.readLine()); //테스트 케이스 횟수
        for (int i = 0; i < n; i++) {
            cnt = 0;
            l = Integer.parseInt(br.readLine());
            graph = new int[l][l];
            visited = new int[l][l];
            st = new StringTokenizer(br.readLine());
            s1 = Integer.parseInt(st.nextToken());
            s2 = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            e1 = Integer.parseInt(st.nextToken());
            e2 = Integer.parseInt(st.nextToken());

            if(isEnd(s1,s2)){
                sb.append(0).append("\n");
            } else {
                visited[s1][s2] = 1;
                bfs();
                sb.append(graph[e1][e2]).append("\n");
            }
        }

        System.out.println(sb);
    }

    public static void bfs() {
        queue = new LinkedList<>();
        queue.offer(new Point(s1, s2));
        int[] dx = {-1, -2, -2, -1, 1, 2, 2, 1};
        int[] dy = {-2, -1, 1, 2, 2, 1, -1, -2};

        while(!queue.isEmpty()) {
            Point curr = queue.poll();

            for(int i = 0; i < 8; i++) {
                int nx = curr.x + dx[i];
                int ny = curr.y + dy[i];
                if(canGo(nx, ny)){
                    if(visited[nx][ny] == 0){
                        queue.offer(new Point(nx,ny));
                        graph[nx][ny] = graph[curr.x][curr.y] + 1;
                        visited[nx][ny] = 1;
                    }

                }
            }
        }
    }

    public static boolean canGo(int x, int y) {
        return 0 <= x && x<l && 0 <= y && y<l;
    }

    public static boolean isEnd(int x, int y){
        return x == e1 && y == e2;
    }
}

class Point {
    int x;
    int y;

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

 

회고 & 배운점

* BFS 공부 (https://www.notion.so/dev-if/f2a7fe2bdc3b4878aef9442fe5ff0d20?pvs=4#51fe65b400d04edcb21f58396e7bf82d)

* 코드를 설계한 후, 풀이를 진행하니 훨씬 풀 때 집중도 되고 부족한 부분을 바로 체크할 수 있었음.

* sb.append(graph[e1][e2]).append("\n") 처럼 stringBuilder로 시간 줄일 수 있었음.