인프런 커뮤니티 질문&답변

이승환님의 프로필 이미지

작성한 질문수

자바 코딩테스트 - it 대기업 유제

6. "숲속의 기사" 코드 해설

혼자서 푼 문제 확인 부탁드립니다.

23.12.09 17:47 작성

·

173

·

수정됨

0

package com.company.대기업유제.너비우선탐색;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class 숲속의기사 {

    static class Pos {

        int x;
        int y;

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

    public int solution(int[][] board) {
        int answer = Integer.MAX_VALUE;

        /**
         * 영희는 궁전에서 기사가 지키는 숲을 통과해서 나가야함
         * 안전하게 가기위해 기사에게 산딸기를 줘야함
         * 최대한 빨리 기사에게 산딸기를 줘야함
         * 숲의 지도: R * C 판 형태
         * 영희 시작위치, 기사 위치, 산딸기 위치가 표시, 영희가 가지 못하는 위치
         * 영희는 산딸기 없이 기사를 지나쳐갈수없음
         * 동서남북 하루에 한칸씩 이동
         * 영희가 산딸기를 기사에게 가져다주는 가장 짧은 날의 수
         * 0 : 영희가 움직일수 있는곳
         * 1: 영희가 움직일수 없는곳
         * 2. 영희의 시작위치
         * 3: 숲속기사의 위치
         * 4: 산딸기 위치
         *
         * */

        //산딸기 위치 저장
        List<Pos> strawberryList = new ArrayList<>();

        for (int i = 0; i < board.length; i++) {

            for (int j = 0; j < board[i].length; j++) {

                if (board[i][j] == 4) {

                    strawberryList.add(new Pos(j, i));
                }
            }
        }

        for (Pos pos : strawberryList) {

            //* 2. 영희의 시작위치
            int count1 = BFS(pos.y, pos.x, board, 2);

            //* 3: 숲속기사의 위치
            int count2 = BFS(pos.y, pos.x, board, 3);

            answer = Math.min(count1 + count2, answer);
        }

        return answer;
    }

    private static int BFS(int y, int x, int[][] board, int posType) {
        //산딸기 위치들로부터 영희의 최소거리, 기사의 최소거리 BFS 각각 한번씩 돌기

        Queue<Pos> queue = new ArrayDeque<>(); //BFS를 위한 queue

        queue.add(new Pos(x, y));

        int[] dx = new int[]{-1, 0, 1, 0};
        int[] dy = new int[]{0, -1, 0, 1};
        boolean[][] ch = new boolean[board.length][board[0].length];
        int day = 0;

        while (!queue.isEmpty()) {

            int size = queue.size();

            for (int i = 0; i < size; i++) {

                Pos pos = queue.poll(); //현재위치로부터

                if(board[pos.y][pos.x] == posType) return day;

                for (int j = 0; j < 4; j++) { //동서남북 이동

                    int moveX = pos.x + dx[j];
                    int moveY = pos.y + dy[j];

                    if (moveY < 0 || moveX < 0 || moveX >= board[0].length || moveY >= board.length) continue;
                    if(ch[moveY][moveX]) continue;
                    if (board[moveY][moveX] == 1) continue;//1: 영희가 움직일수 없는곳

                    ch[moveY][moveX] = true;
                    queue.add(new Pos(moveX, moveY));
                }
            }

            day++;
        }

        return -1;
    }

    public static void main(String[] args) {
        숲속의기사 T = new 숲속의기사();
        System.out.println(T.solution(new int[][]{{4, 1, 0, 0, 0, 0, 1, 0},
                {0, 0, 0, 1, 0, 1, 0, 0},
                {0, 2, 1, 1, 3, 0, 4, 0},
                {0, 0, 0, 4, 1, 1, 1, 0}}));
       System.out.println(T.solution(new int[][]{{3, 0, 0, 0, 1, 4, 4, 4},
          {0, 1, 1, 0, 0, 0, 1, 0},
          {0, 1, 4, 0, 1, 0, 0, 0},
          {0, 0, 0, 1, 0, 0, 0, 0},
          {1, 0, 1, 0, 0, 1, 1, 0},
          {4, 0, 0, 0, 1, 0, 0, 0},
          {4, 1, 0, 0, 1, 0, 0, 0},
          {4, 0, 0, 0, 0, 0, 1, 2}}));
       System.out.println(T.solution(new int[][]{{4, 1, 0, 1, 0},
          {0, 1, 0, 1, 0},
          {0, 0, 2, 3, 4},
          {0, 1, 0, 1, 0}}));
    }
}


딸기위치를 기준으로 영희와 숲속의 기사의 최단거리를 각각 따로 BFS로 구하였는데 괜찮은 방법인가요?

답변 2

0

김태원님의 프로필 이미지
김태원
지식공유자

2023. 12. 11. 20:48

안녕하세요^^

위 방법은 산딸기가 많은 입력은 BFS호출이 많아져 효율성이 떨어지게 됩니다.

영상의 방법은 산딸기의 개수와 상관없이 BFS호출을 2번만 하는 방법이니 영상의 방법을 추천합니다.

이승환님의 프로필 이미지
이승환
질문자

2023. 12. 12. 12:47

아~ 그럴수있겠네요! 감사합니다

0

인프런 AI 인턴님의 프로필 이미지

2023. 12. 11. 17:54

안녕하세요, 인프런 AI 인턴입니다.

님의 코드를 보니, 주어진 문제를 해결하기 위해 영희의 시작 위치와 숲속의 기사 위치를 연결하기 위해 두 위치 사이의 최단 거리를 BFS(너비 우선 탐색)를 통해 각각 구한 후, 두 거리를 합하여 최소값을 찾는 접근을 하셨습니다. 이는 산딸기를 거쳐 기사에게 도달해야 한다는 문제의 조건을 충실히 반영한 유효한 방법입니다.

산딸기 위치에서 시작하여 영희의 위치와 숲속의 기사 위치까지의 거리를 각각 구한 다음, 이들의 합이 최소가 되는 경우를 찾는 것은 주어진 문제 상황을 해결하는 데 있어 알맞는 접근입니다.

단, 조건 중 ‘영희는 산딸기 없이 기사를 지나쳐갈 수 없다’는 점을 고려할 때, 산딸기를 먼저 방문한 후 숲속의 기사에게 도달하는 경로만을 고려해야 한다는 점을 주의하시는 것이 중요합니다.

따라서 구현하신 BFS 함수에서는 장애물(1)을 피해 이동하며, 영희의 시작 위치나 숲속의 기사 위치 등의 특정 지점까지의 최단 거리만 계산하되, 이미 방문한 위치를 다시 방문하지 않도록 ch라는 방문 배열을 사용한 것도 적합한 것으로 보입니다.

코드에서 BFS 함수가 각 산딸기 위치에 대해 두 번 호출됨에 따라 모든 산딸기 위치에 대해 영희의 시작 위치와 숲속의 기사 위치까지의 최단 거리를 찾고, 그 중 최소 값을 정답으로 반환하는 로직도 문제 해결 방식에 적절합니다.

결론적으로, 님의 접근 방법은 주어진 문제를 해결하는 데 있어 적절한 방법이며, BFS를 통해 구현한 알고리즘 역시 잘 동작할 것으로 예상됩니다. 다만, 항상 예외 상황에 대해 충분히 테스트를 진행해보고, 성능상의 개선 여지가 있는지 확인하는 것을 권장드립니다.