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

1. 문제 풀이 아이디어

• BFS를 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    public int[] solution(String[] maps) {
        List<Integer> list = new ArrayList<>();
        int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        boolean[][] visited = new boolean[maps.length][maps[0].length()];
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[i].length(); j++) {
                if (visited[i][j]) continue;
                visited[i][j] = true;
                if (maps[i].charAt(j) == 'X') continue;
                queue.add(new int[]{i, j});
                int count = Character.getNumericValue(maps[i].charAt(j));
                while (!queue.isEmpty()) {
                    int[] cur = queue.poll();
                    for (int k = 0; k < dir.length; k++) {
                        int nx = cur[0] + dir[k][0];
                        int ny = cur[1] + dir[k][1];
                        if (nx < 0 || ny < 0 || nx >= maps.length || ny >= maps[nx].length() || visited[nx][ny])
                            continue;
                        visited[nx][ny] = true;
                        if (maps[nx].charAt(ny) == 'X') continue;
                        count += Character.getNumericValue(maps[nx].charAt(ny));
                        queue.add(new int[]{nx, ny});
                    }
                }
                list.add(count);
            }
        }
        if (list.size() == 0) return new int[]{-1};
        return list.stream().mapToInt(i -> i).sorted().toArray();
    }
}

3. 정리

• visited 배열을 생성하여 각 위치의 방문 여부를 확인한다.

• 모든 위치를 순회하며 다음 과정을 수행한다.
• 방문하지 않았고, 값이 X가 아닌 경우 BFS를 시작한다.
• BFS를 통해 연결된 영역을 탐색하며, 값의 합을 계산한다.
• 큐를 사용하여 현재 위치의 상하좌우를 탐색한다.
• 범위를 벗어나거나, 이미 방문한 위치, 값이 X인 경우는 제외한다.
• 탐색이 완료되면, 합산 값을 리스트에 추가한다.

• 리스트가 비어 있으면 [-1]을 반환하고, 그렇지 않으면 정렬하여 배열로 변환한 결과를 반환한다.