[pg] 프로그래머스 무인도 여행

1. 문제 정의

 전형적인 bfs / dfs 문제.

 맵이 주어지고 맵 안에는 무인도와 바다가 있으며, 바다칸에는 X,  무인도칸에는 1~9의 숫자가 주어진다. 무인도가 인접해 있다면 하나의 무인도라고 정의한다. 

 최종적으로는 맵 안에 있는 무인도들이 가지고 있는 식량들의 값을 오름차순으로 정렬해서 리턴하는 문제이다.(무인도의 갯수는 0~N)

무인도가 없을 경우에는 -1을 리턴한다.

 

2. 내가 한 시도

 처음 문제를 보고 전형적인 bfs / dfs 문제라는 것을 깨달았다. 나같은 경우는 dfs보다는 bfs로 문제를 푸는 것이 편해서 bfs로 풀기로 결정하고, 로직을 작성했다.

 이 문제의 특징이라고 할 수 있는 것은 이전에 탐색했던 루트를 다시 탐색하지 않기 위해서 visited를 전역변수로 공유해서 사용해야 했던 점이다.

 그 이외에는 X가 벽, 숫자는 탐색해야할 자리 라는 것을 인식하고 bfs로 문제를 풀었다면 쉽게 풀리는 문제라고 생각한다.

 

3. 코드

import java.util.*;

/**
 * 프로그래머스 LV2
 * 무인도 여행
 * 접근 방법: bfs로 해결
 */
public class Solution {
    public static void main(String[] args) {
        int[] solution = solution(new String[]{"X591X", "X1X5X", "X231X", "1XXX1"});
        for (int i : solution) {
            System.out.println(i);
        }
    }


    public static int[] solution(String[] input) {
        List<Integer> foods = new ArrayList<>(); // 무인도 당 식량값을 저장할 리스트
        char[][] maps = new char[input.length][input[0].length()]; // 2차원 배열로 변경
        int[][] visited = new int[input.length][input[0].length()]; // 방문여부 확인용


        /*
         * 바다와 무인도를 visited에 기록 및 이차원 배열로 변경한 maps에 내용 채워주기 -> 지도 완성
         */
        for (int i = 0; i < input.length; i++) {
            char[] chars = input[i].toCharArray();
            for (int j = 0; j < chars.length; j++) {
                maps[i][j] = chars[j];
                if (maps[i][j] == 'X') {
                    visited[i][j] = 1;
                }
            }
        }

        /*
         * 지도를 탐색하면서 무인도를 발견하면 탐색 후 식량 값을 List에 저장
         */
        for (int i = 0; i < maps.length; i++) {
            char[] map = maps[i];
            for (int j = 0; j < map.length; j++) {
                char c = map[j];
                if (c != 'X') {
                    foods.add(bfs(maps, visited, i, j));
                }
            }
        }
        if(foods.isEmpty()) return new int[] {-1}; // 무인도가 없으면 -1 리턴
        Collections.sort(foods); // 오름차순 정렬
        return foods.stream().mapToInt(i->i).toArray();
    }

    public static int bfs(char[][] maps, int[][] visited, int startX, int startY) {
        int[] nx = {0, 0, -1, 1};
        int[] ny = {-1, 1, 0, 0};

        Queue<int[]> queue = new LinkedList<>();

        queue.offer(new int[]{startX, startY}); // bfs 시작점 (무인도 탐색 시작)
        visited[startX][startY] = 1;
        int food = Character.getNumericValue(maps[startX][startY]); // 무인도의 식량 값

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            for (int i = 0; i < 4; i++) {
                if (poll[0] + nx[i] < 0 || poll[0] + nx[i] >= maps.length ||
                        poll[1] + ny[i] < 0 || poll[1] + ny[i] >= maps[0].length) {
                    continue;
                }
                if (visited[poll[0] + nx[i]][poll[1] + ny[i]] != 1) {
                    food += Character.getNumericValue(maps[poll[0] + nx[i]][poll[1] + ny[i]]);
                    queue.offer(new int[]{poll[0] + nx[i], poll[1] + ny[i]});
                    visited[poll[0] + nx[i]][poll[1] + ny[i]] = 1;
                    maps[poll[0] + nx[i]][poll[1] + ny[i]] = 'X';
                }
            }
        }
        return food;
    }

}

 

4. 회고

 이제 bfs/dfs 문제도 꽤나 익숙해진 모양이다. 거의 정형화된 틀에 조금만 응용을 한다면 풀 수 있는 수준이 된 것 같다. 그래도 아직까진 디버깅을 해봐야하는 문제들이라 조금 더 연습이 필요할 듯 하다.

 

 

참조

https://school.programmers.co.kr/learn/courses/30/lessons/154540