[프로그래머스] 무인도 여행 자바 (Level 2) BFS

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/154540

1. 문제 요약

• 바다 ‘X’로 구분된 지도에서 숫자로 연결된 섬을 구분한다
• 구분된 섬들의 내부숫자의 합 구하기

2. 핵심 아이디어

• BFS방식으로 ‘X’가 아닌 연결된 값들의 합 구하기

3. 풀이 코드

/**
     *
     * @param maps 'X' : 바다 1~9 : 무인도.
     * @return 각 연결된 숫자그룹(무인도)내의 합 오름차순
     */
    public int[] solution(String[] maps) {
        int rows = maps.length, cols = maps[0].length();

        boolean[][] visited = new boolean[rows][cols];
        int[] dx = {0,0,-1,1}, dy = {1,-1,0,0};

        List<Integer> results = new ArrayList<>(); // 각 섬들의 합

        for(int i = 0; i < rows; i ++){
            for(int j = 0; j < cols; j ++) {
                //최초방문구역 && 바다가 아님
                if(!visited[i][j] && maps[i].charAt(j) != 'X'){
                    Queue<int[]> q = new LinkedList<>();
                    q.add(new int[]{i, j});
                    visited[i][j] = true;
                    int sum = maps[i].charAt(j) - '0';

                    //인접구역 탐방
                    while(!q.isEmpty()){
                        int[] cur = q.poll();
                        int x = cur[0], y = cur[1];
                        for(int d = 0; d < 4; d++){
                            int nx = x + dx[d], ny = y + dy[d];

                            //지도범위 이내 && 미방문 && 바다가 아님
                            if(nx >= 0 && ny >= 0 && nx < rows && ny < cols &&
                            !visited[nx][ny] && maps[nx].charAt(ny) != 'X'){
                                visited[nx][ny] = true;
                                q.add(new int[]{nx, ny});
                                sum += maps[nx].charAt(ny) - '0';
                            }
                        }
                    }
                    results.add(sum);
                }
            }
        }

        if(results.isEmpty()) return new int[]{-1};

        Collections.sort(results);
        return results.stream().mapToInt(Integer::intValue).toArray();
    }

 

4. 회고 및 느낀점

• BFS방식은 다른 문제와 유사했지만 출발점이 따로 정해져있지 않아 코드생김새가 다소 차이가 있는 것으로 보임.