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

문제

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

프로그래머스

 

문제 분석

제한사항

3<= maps 의 길이 <= 100

• 3<= maps[i] 의 길이 <= 100
• maps[i] 는 'X' 또는 1과 9 사이의 자연수로 이루어진 문자열입니다.
• 지도는 직사각형 형태입니다.

X 와 숫자로 이루어진 맵이 주어진다.

X 는  바다, 숫자는 식량의 개수를 나타낸다. 

 

위의 맵에는 총 3개의 섬으로 이루어져 있고 각각의 섬의 식량을 계산해보면 [1, 1, 27] 이다.

이런 방식으로 맵이 주어졌을 때 모든 섬의 식량 개수를 계산하는 문제이다.

 

 

문제 접근

이 문제를 풀기 위해서는 주어진 맵에서 인접한 숫자들의 합을 구한 다음 정렬하면 쉽게 해결될 거 같다.

인접한 숫자들을 찾기 위해서는 BFS 나 DFS 를 사용하면 된다. 

여기서는 BFS 로 문제를 풀어 보겠다.

 

1. 주어진 정보를 사용하기 편한 형태로 만든다.
2. 맵을 방문하면서 방문하지 않았고 육지라면 BFS 로 연결된 육지를 모두 방문한다.
 - 연결된 모든 육지를 방문하면서 식량을 계산한다.
 - 연결된 모든 육지 방문이 끝나면 계산된 식량을 정답 리스트에 담아둔다.
3. 정답 리스트가 비었다면 -1을 반환하고 아니면 정답 리스트를 정렬하여 반환한다

코드

import java.util.*;

class Solution {
    static final int[][] moves = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static List<Integer> resultList = new ArrayList<>();
    public int[] solution(String[] maps) {
        int[][] map = new int[maps.length][maps[0].length()];
        boolean[][] visited = new boolean[map.length][map[0].length];

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (maps[i].charAt(j) == 'X') {
                    map[i][j] = -1;
                }else{
                    map[i][j] = Integer.parseInt(maps[i].charAt(j) + "");
                }
            }
        }

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (!visited[i][j] && map[i][j] != -1) {
                    bfs(i, j, map, visited);
                }
            }
        }
        
        if (resultList.size() == 0) {
            return new int[]{-1};
        }

        Collections.sort(resultList);

        return resultList.stream().mapToInt(Integer::intValue).toArray();
    }
    
    public static void bfs(int r, int c, int[][] map, boolean[][] visited){
        int sum = 0;
        Queue<int[]> queue = new LinkedList<>();

        queue.offer(new int[]{r, c});
        visited[r][c] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            sum += map[cur[0]][cur[1]];

            for (int[] move : moves) {
                int nextR = cur[0] + move[0];
                int nextC = cur[1] + move[1];

                if (nextR >= 0 && nextR < map.length && nextC >= 0 && nextC < map[0].length) {
                    if (map[nextR][nextC] != -1 && !visited[nextR][nextC]) {
                        queue.offer(new int[]{nextR, nextC});
                        visited[nextR][nextC] = true;
                    }
                }
            }
        }
        resultList.add(sum);
    }
}