[알고리즘풀이]백준 18404 : 현명한 나이트 JAVA

목차

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

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 18404번 현명한 나이트를 풀었습니다. 이를 정리해보고자 합니다.

18404번: 현명한 나이트

 

본문

1) 문제

2) 과정

나이트 이동 문제 (7562)를 풀고나서 이 문제를 풀었더니 그저 7562에 출력해야할 케이스의 수가 증가한 정도의 문제였습니다. 그래도 다시한번 풀어보자 하는 마음으로 처음부터 풀었는데 결과적으론 비슷하더라구요... 

더 다양한 방식으로 접근할 수 있는 힘을 키워야겠다는 생각을 갖게한 문제였습니다!

 

이번 문제 해설은 input, initialize, logic, output이 들어있는 main과 Inner Class인 Node로 구성했습니다.

최근부터는 문제를 풀고 설명을 직접 달아보는 방식이 남들에게 직접 설명하듯이 문제를 풀어볼 수 있어서 공부에도 도움이 되고 코드도 정리해보고 아래 사진과 같은 경우를 방지할 수도 있어서 주석을 통해 미리 설명을 달아두었습니다!

 

2-1) main

    // 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}; // 시계방향으로 나이트가 이동할 수 있는 x값
    private static final int[] yDiff = {2,1,-1,-2,-2,-1,1,2}; // 시계방향으로 나이트가 이동할 수 있는 y값

    // Variable
    private static int n, m; // 한 변의 길이, 적의 수
    private static Node knight; // 나이트의 위치
    private static Node[] enemies; // 적의 위치를 담은 배열

    // Main
    public static void main(String[] args) throws IOException{
        // Input
        // 기본정보인 체스판의 한 변 길이와 적의 수를 n,m에 저장
        String[] basicInfo = reader.readLine().split(" ");
        n = Integer.parseInt(basicInfo[0]);
        m = Integer.parseInt(basicInfo[1]);

        // knight의 위치를 받아와 knight 변수에 할당
        String[] knightInfo = reader.readLine().split(" ");
        knight = new Node(Integer.parseInt(knightInfo[0]),Integer.parseInt(knightInfo[1]));

        // enemy의 위치를 받아와 enemies 배열에 할당
        enemies = new Node[m];
        for(int i = 0; i<m;i++){
            String[] enemyInfo = reader.readLine().split(" ");
            Node enemy = new Node(Integer.parseInt(enemyInfo[0]),Integer.parseInt(enemyInfo[1]));
            enemies[i] = enemy;
        }

        // Initialize
        // knight의 이동하는 거리를 계산
        int[][] dp = new int[n+1][n+1];

        // 방문한 적 있는지 여부 저장 (knight의 시작위치 방문 체크)
        boolean[][] visited = new boolean[n+1][n+1];
        visited[knight.x][knight.y] = true;

        // knight가 움직일 케이스들을 담은 큐 생성 + 큐에 현재 나이트 위치 추가
        Queue<Node> knightQueue = new LinkedList<>();
        knightQueue.add(knight);

        // Logic
        while(!knightQueue.isEmpty()){
            // 나이트 하나를 가져옴.
            Node tmpKnight = knightQueue.poll();

            for(int i=0;i<8;i++){
                // 나이트가 갈 수 있는 좌표를 가져온다.
                Node tmp = tmpKnight.add(xDiff[i], yDiff[i]);

                // 범위 체크 (범위를 벗어나는지 체크)
                if(!checkBound(tmp)) continue; 

                // 방문 여부 체크 (방문했던 곳인지 체크)
                if(visited[tmp.x][tmp.y]) continue;
                visited[tmp.x][tmp.y] = true;

                // dp값(해당 좌표까지의 최소 이동횟수) 넣기.(bfs + visited이기 때문에 현재 저장값과 새로운 값의 비교는 필요없다.)
                dp[tmp.x][tmp.y] = dp[tmpKnight.x][tmpKnight.y]+1;

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

        // Output
        String sb = "";
        for(int i=0;i<m;i++){
            // 띄어쓰기로 각 적들까지의 최소 이동 수를 담는다. 
            Node enemy = enemies[i];
            sb+=dp[enemy.x][enemy.y]+" ";
        }
        System.out.println(sb.stripTrailing());
    }

    // Method
    // x와 y좌표가 0~n으로 체스판 위에 있는지 체크하는 함수
    private static boolean checkBound(Node node){return 0<node.x && node.x<=n && 0<node.y && node.y<=n;}

 

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

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

 

2-2) Inner Class

    // Inner Class
    // 나이트의 좌표(x,y)를 담음.
    private static class Node{
        int x,y;
        public Node(int x,int y){
            this.x= x;
            this.y= y;
        }

        // 현재 노드의 x,y에 파라미터로 받은 x,y를 더한 위치의 새 노드를 리턴한다.
        public Node add(int x, int y){
            int tmpX = this.x+x;
            int tmpY = this.y+y;
            return new Node(tmpX,tmpY);
        }

    }

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

    // 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}; // 시계방향으로 나이트가 이동할 수 있는 x값
    private static final int[] yDiff = {2,1,-1,-2,-2,-1,1,2}; // 시계방향으로 나이트가 이동할 수 있는 y값

    // Variable
    private static int n, m; // 한 변의 길이, 적의 수
    private static Node knight; // 나이트의 위치
    private static Node[] enemies; // 적의 위치를 담은 배열

    // Main
    public static void main(String[] args) throws IOException{
        // Input
        // 기본정보인 체스판의 한 변 길이와 적의 수를 n,m에 저장
        String[] basicInfo = reader.readLine().split(" ");
        n = Integer.parseInt(basicInfo[0]);
        m = Integer.parseInt(basicInfo[1]);

        // knight의 위치를 받아와 knight 변수에 할당
        String[] knightInfo = reader.readLine().split(" ");
        knight = new Node(Integer.parseInt(knightInfo[0]),Integer.parseInt(knightInfo[1]));

        // enemy의 위치를 받아와 enemies 배열에 할당
        enemies = new Node[m];
        for(int i = 0; i<m;i++){
            String[] enemyInfo = reader.readLine().split(" ");
            Node enemy = new Node(Integer.parseInt(enemyInfo[0]),Integer.parseInt(enemyInfo[1]));
            enemies[i] = enemy;
        }

        // Initialize
        // knight의 이동하는 거리를 계산
        int[][] dp = new int[n+1][n+1];

        // 방문한 적 있는지 여부 저장 (knight의 시작위치 방문 체크)
        boolean[][] visited = new boolean[n+1][n+1];
        visited[knight.x][knight.y] = true;

        // knight가 움직일 케이스들을 담은 큐 생성 + 큐에 현재 나이트 위치 추가
        Queue<Node> knightQueue = new LinkedList<>();
        knightQueue.add(knight);

        // Logic
        while(!knightQueue.isEmpty()){
            // 나이트 하나를 가져옴.
            Node tmpKnight = knightQueue.poll();

            for(int i=0;i<8;i++){
                // 나이트가 갈 수 있는 좌표를 가져온다.
                Node tmp = tmpKnight.add(xDiff[i], yDiff[i]);

                // 범위 체크 (범위를 벗어나는지 체크)
                if(!checkBound(tmp)) continue; 

                // 방문 여부 체크 (방문했던 곳인지 체크)
                if(visited[tmp.x][tmp.y]) continue;
                visited[tmp.x][tmp.y] = true;

                // dp값(해당 좌표까지의 최소 이동횟수) 넣기.(bfs + visited이기 때문에 현재 저장값과 새로운 값의 비교는 필요없다.)
                dp[tmp.x][tmp.y] = dp[tmpKnight.x][tmpKnight.y]+1;

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

        // Output
        String sb = "";
        for(int i=0;i<m;i++){
            // 띄어쓰기로 각 적들까지의 최소 이동 수를 담는다. 
            Node enemy = enemies[i];
            sb+=dp[enemy.x][enemy.y]+" ";
        }
        System.out.println(sb.stripTrailing());
    }

    // Method
    // x와 y좌표가 0~n으로 체스판 위에 있는지 체크하는 함수
    private static boolean checkBound(Node node){return 0<node.x && node.x<=n && 0<node.y && node.y<=n;}

    // Inner Class
    // 나이트의 좌표(x,y)를 담음.
    private static class Node{
        int x,y;
        public Node(int x,int y){
            this.x= x;
            this.y= y;
        }

        // 현재 노드의 x,y에 파라미터로 받은 x,y를 더한 위치의 새 노드를 리턴한다.
        public Node add(int x, int y){
            int tmpX = this.x+x;
            int tmpY = this.y+y;
            return new Node(tmpX,tmpY);
        }

    }

}

 

제가 문제를 풀며 걸렸던 소요시간, 아이디어, 에러로그 등 더 자세히 코드를 보고싶으시다면, 아래 깃헙링크를 확인해주세요.

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

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