[알고리즘풀이]백준 7562 : 나이트의 이동 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 7562번 나이트의 이동을 풀었습니다. 이를 정리해보고자 합니다.

7562번: 나이트의 이동

 

본문

1) 문제

2) 과정

이번 문제를 푸는 데는 1시간 정도 걸렸습니다.

말을 이동시키는 것도 큐를 이용해 bfs를 구현하는것도 어느 정도 적응이 되어 그렇게 어렵거나 오래걸린 문제는 아니었습니다.

 

2-1) main

 public static void main(String[] args) throws IOException{
        // Input
        int testcase = Integer.parseInt(reader.readLine()); // 테스트 케이스의 수
        for(int loop = 0 ; loop< testcase; loop++){
            size = Integer.parseInt(reader.readLine()); // 체스의 한 변의 크기

            String[] sLine = reader.readLine().split(" "); // 시작 위치
            Node start = new Node(Integer.parseInt(sLine[0]),Integer.parseInt(sLine[1]));

            String[] eLine = reader.readLine().split(" "); // 종료 위치
            Node end = new Node(Integer.parseInt(eLine[0]),Integer.parseInt(eLine[1]));

            // Initialize
            int[][] dp = new int[size][size]; // 최소 이동횟수를 담는다.

            boolean[][] visited = new boolean[size][size]; // 방문 여부를 담는다.

            Queue<Node> kQueue = new LinkedList<>(); // 각 나이트들의 위치를 담는다.
            visited[start.x][start.y] = true; // 시작 위치 방문 true로 셋팅(시작과 종료의 위치가 같을 때 다른 곳을 다녀오지 않도록 해야하기 때문에)
            kQueue.add(start); // 시작 위치 큐에 담기

            // Logic
            while(!kQueue.isEmpty()){
                // 큐에서 좌표 가져오기
                Node node = kQueue.poll();

                for(int i=0;i<8;i++){ // 나이트의 이동가능한 위치를 모두 탐색
                    // 임시 좌표 설정
                    int tmpX = node.x+xDiff[i];
                    int tmpY = node.y+yDiff[i];
                    Node tmp = new Node(tmpX, tmpY);

                    // 범위 체크(체스판을 벗어나는지 여부)
                    if(!checkBound(tmp)) continue;

                    // 방문 체크(이미 방문했던 위치인지 여부 - bfs이기 때문에 계속 커지는 count의 특성 상 더 작은 경우가 나올 수 없어 visited면 다시 방문하지 않도록 체크)
                    if(visited[tmpX][tmpY]) continue;
                    visited[tmpX][tmpY] = true;

                    // dp값(해당 좌표까지의 최소 이동횟수) 넣기.
                    dp[tmpX][tmpY] = dp[node.x][node.y]+1;

                    // 큐에 넣어 더이상 탐색할 수 없을 때까지 탐색 진행.
                    kQueue.add(tmp);
                }

            }

            // Output
            System.out.println(dp[end.x][end.y]);
        }
    }
    
    
    // Method
    private static boolean checkBound(Node node){return 0<=node.x && node.x<size && 0<=node.y && node.y<size;}

이번엔 문제를 푼 후 주석으로 설명을 첨부하였습니다.

주석을 보고 이해안되거나 어려웠던 부분이 있으시다면 댓글 남겨주시면 감사하겠습니다.

 

읽어오는 것 관련된 정보는 아래 링크를 확인해주세요 :)

[개념정리] System.in / InputStreamReader / BufferedReader 정리

2-2) Inner Class

    // Inner Class
    private static class Node{
        int x, y;
        public Node(int x, int y){
            this.x=x;
            this.y=y;
        }
    }
}

Inner Class로 말의 좌표를 담는 Node 클래스는 위와 같습니다. 단순하게 x와 y를 함께 저장할 수 있도록 구성하였습니다.

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

package sujeong.dfs_bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ7562 {

    // Attribute
    private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    // Constants
    private static final int[] xDiff = {1,2,2,1,-1,-2,-2,-1};
    private static final int[] yDiff = {2,1,-1,-2,-2,-1,1,2};

    // Variable
    private static int size; // 체스 한 변의 크기

    // Main
    public static void main(String[] args) throws IOException{
        // Input
        int testcase = Integer.parseInt(reader.readLine()); // 테스트 케이스의 수
        for(int loop = 0 ; loop< testcase; loop++){
            size = Integer.parseInt(reader.readLine()); // 체스의 한 변의 크기

            String[] sLine = reader.readLine().split(" "); // 시작 위치
            Node start = new Node(Integer.parseInt(sLine[0]),Integer.parseInt(sLine[1]));

            String[] eLine = reader.readLine().split(" "); // 종료 위치
            Node end = new Node(Integer.parseInt(eLine[0]),Integer.parseInt(eLine[1]));

            // Initialize
            int[][] dp = new int[size][size]; // 최소 이동횟수를 담는다.

            boolean[][] visited = new boolean[size][size]; // 방문 여부를 담는다.

            Queue<Node> kQueue = new LinkedList<>(); // 각 나이트들의 위치를 담는다.
            visited[start.x][start.y] = true; // 시작 위치 방문 true로 셋팅(시작과 종료의 위치가 같을 때 다른 곳을 다녀오지 않도록 해야하기 때문에)
            kQueue.add(start); // 시작 위치 큐에 담기

            // Logic
            while(!kQueue.isEmpty()){
                // 큐에서 좌표 가져오기
                Node node = kQueue.poll();

                for(int i=0;i<8;i++){ // 나이트의 이동가능한 위치를 모두 탐색
                    // 임시 좌표 설정
                    int tmpX = node.x+xDiff[i];
                    int tmpY = node.y+yDiff[i];
                    Node tmp = new Node(tmpX, tmpY);

                    // 범위 체크(체스판을 벗어나는지 여부)
                    if(!checkBound(tmp)) continue;

                    // 방문 체크(이미 방문했던 위치인지 여부 - bfs이기 때문에 계속 커지는 count의 특성 상 더 작은 경우가 나올 수 없어 visited면 다시 방문하지 않도록 체크)
                    if(visited[tmpX][tmpY]) continue;
                    visited[tmpX][tmpY] = true;

                    // dp값(해당 좌표까지의 최소 이동횟수) 넣기.
                    dp[tmpX][tmpY] = dp[node.x][node.y]+1;

                    // 큐에 넣어 더이상 탐색할 수 없을 때까지 탐색 진행.
                    kQueue.add(tmp);
                }

            }

            // Output
            System.out.println(dp[end.x][end.y]);
        }
    }

    // Method
    private static boolean checkBound(Node node){return 0<=node.x && node.x<size && 0<=node.y && node.y<size;}

    // Inner Class
    private static class Node{
        int x, y;
        public Node(int x, int y){
            this.x=x;
            this.y=y;
        }
    }
}

 

소요시간, 아이디어, 에러로그 등 더 자세히 보고싶으시다면, 아래 깃헙 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/dfs_bfs/BOJ7562.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비