[Algorithm] BOJ-7562 Java로 문제풀이 (BFS)

---

안녕하세요 Coding-Knowjam입니다.

오늘은 BFS알고리즘을 이용해서 문제를 풀어보겠습니다.

백준 온라인 저지에 있는 문제를 풀어볼 예정이며 문제와 관련한 내용은 링크를 참조하시면 되겠습니다.

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

 

1. 해결 아이디어

문제 자체는 기본적인 BFS를 구현할 수 있다면 어렵지 않게 풀 수 있습니다.

문제를 풀기 위한 아이디어는 다음과 같습니다.

• 나이트가 이동하는 좌표를 계산할 수 있도록 move배열 선언
• 나이트가 방문한 좌표는 다시 방문하지 않음

 

2. Java 코드로 구현

우선 코드로 구현할 때 아마 개발자마다 성향이 다르겠지만 저는 2차원 배열 안에서 움직이는 좌표를 계산할 때 클래스를 따로 선언해주는 것이 편해서 이번에도 클래스를 하나 만들어보겠습니다.

static class Node{
        int x;          // x좌표
        int y;          // y좌표
        int count;      // 최소 이동횟수를 구할 변수

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

클래스는 위와 같이 각각의 좌표값을 저장할 변수와 최소 이동 횟수를 구하기 위한 카운트 변수를 가지고 있습니다.

내부 클래스로 만들 거라서 getter나 setter 같은 메서드는 따로 선언하지 않았습니다.

다음으로 BFS알고리즘을 이용해서 실제 나이트의 최소 이동 횟수를 계산하는 로직을 구현해보겠습니다.

 

public static void main(String[] args) throws IOException {
        // 입출력을 담당할 BufferedReader, BufferedWriter
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 테스트케이스 개수 저장
        int testCaseCount = Integer.parseInt(br.readLine());
        
        // 나이트의 이동 좌표를 계산하기 위한 배열
        int[] moveX = {-2, -2, 2, 2, -1, -1, 1, 1};
        int[] moveY = {-1, 1, -1, 1, -2, 2, -2, 2};

        // 테스트케이스 개수 만큼 반복
        for(int i=0; i<testCaseCount; i++){
            // BFS를 위해 사용할 Queue
            Queue<Node> q = new LinkedList<>();
            
            // 체스판의 크기 값 저장
            int mapSize = Integer.parseInt(br.readLine());
            
            // 나이트가 방문했는지 여부 체크를 위한 2차원 배열
            boolean[][] map = new boolean[mapSize][mapSize];
            
            // 나이트가 처음에 서있는 위치 저장
            String[] start = br.readLine().split(" ");
            
            // 나이트가 도착해야 할 위치 저장
            String[] end = br.readLine().split(" ");

            // 처음 시작 지점의 좌표와 이동횟수 정보를 가지는 Node객체 생성
            Node startNode = new Node(Integer.parseInt(start[0]), Integer.parseInt(start[1]), 0);
            
            // Queue에 시작지점의 객체 넣기
            q.offer(startNode);
            
            // 나이트가 서있는 시작지점 방문처리
            map[startNode.x][startNode.y] = true;
            
            // Queue가 빌 때가지 반복
            while(!q.isEmpty()){
                
                // Queue에서 Node 객체 꺼내기
                Node node = q.poll();
                
                // 꺼낸 Node의 현재 좌표 값 변수에 저장
                int x = node.x;
                int y = node.y;
                
                // Queue에서 꺼낸 Node의 현재 위치가 도착할 지점과 같다면, 현재까지 이동횟수 bw에 저장
                if (x == Integer.parseInt(end[0]) && y == Integer.parseInt(end[1])) {
                    bw.write(String.valueOf(node.count));
                    bw.newLine();
                    break;
                }

                // 다음 위치로 이동하기 위한 계산시작
                for (int j=0; j<moveX.length; j++){
                    // 현재 Node객체가 있는 좌표 값을 기준으로 다음 x,y좌표 계산
                    int movex = node.x + moveX[j];
                    int movey = node.y + moveY[j];
        
                    // 만약에 다음에 이동 할 x,y좌표가 체스판을 벗어나거나, 방문했던 적이 있다면 좌표값 다시 계산
                    if(movex < 0 || movex >= mapSize || movey < 0 || movey >= mapSize || map[movex][movey]){
                        continue;
                    }else{
                        // 아니라면 해당 좌표값의 정보를 가지는 객체 생성 (이동 횟수 + 1)
                        q.offer(new Node(movex, movey, node.count + 1));
                        
                        // 다음에 이동 할 위치의 좌표값 방문처리
                        map[movex][movey] = true;
                    }
                }
            }
        }
        // 최소이동횟수 출력
        bw.flush();

    }

소스코드 한줄한줄마다 주석으로 설명을 달아 드렸으니 천천히 읽어보시면 될 것 같습니다.

해당 문제를 풀기 위해 가장 중요한 부분은 나이트의 다음 위치를 계산하기 위한 배열을 만드는 거라 생각합니다.

그 이후는 일반적인 BFS알고리즘을 구현하는 것과 다를 바가 없습니다.

한 가지 아쉬운 점이 Node클래스의 이름은 나이트로 지었으면 코드가 좀 더 문제랑 매칭이 잘 되었을 텐데 다 풀고 나니까 생각이 났네요..ㅎ

읽어주셔서 감사합니다.

---