[Programmers] 무인도 여행 / ⭕

프로그래머스

 

1. 제출 코드 (19분 33초 / BFS)

import java.util.*;

class Solution {
    static ArrayList<Character>[] map;
    static boolean[][] visited;
    
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
    public ArrayList<Integer> solution(String[] maps) {
        ArrayList<Integer> answer = new ArrayList<>();
        map = new ArrayList[maps.length];
        visited = new boolean[maps.length][maps[0].length()];
        for(int i = 0; i < maps.length; i++) {
            map[i] = new ArrayList<>();
            for(int j = 0; j < maps[i].length(); j++) {
                map[i].add(maps[i].charAt(j));
            }
        }
        
        for(int i = 0; i < maps.length; i++) {
            for(int j = 0; j < maps[0].length(); j++) {
                if(map[i].get(j) != 'X' && !visited[i][j]) {
                    visited[i][j] = true;
                    int sum = bfs(i, j);
                    if(sum != 0) {
                        answer.add(sum);
                    }
                }
            }
        }
        if(answer.isEmpty()) {
            answer.add(-1);
        } else {
            answer.sort((o1, o2) -> {
                return o1 - o2;
            });
        }
        return answer;
    }
    
    static int bfs(int x, int y) {
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
        int sum = 0;
        
        while(!q.isEmpty()) {
            int[] t = q.poll();
            
            sum += map[t[0]].get(t[1]) - '0';
            for(int i = 0; i < 4; i++) {
                int nx = t[0] + dx[i];
                int ny = t[1] + dy[i];
                
                if(nx < 0 || nx >= map.length || ny < 0 || ny >= map[0].size() || map[nx].get(ny) == 'X' ||visited[nx][ny]){
                    continue;
                }
                visited[nx][ny] = true;
                q.add(new int[] {nx, ny});
            }
        }
        return sum;
    }
}

 

2. 구현 로직

1. maps의 길이가 최대 100이기 때문에, 최대 10,000개의 노드를 탐색할 수 있어 시간 초과는 문제 없을 것이라 판단하여 모든 노드를 검색
2. 방문한 적이 있거나 'X'를 가지는 땅은 탐색하지 않고 자연수로 이뤄진 땅을 하나 골라 BFS로 주변 탐색
3. BFS로 탐색되는 곳은 하나의 무인도이기 때문에 탐색되는 각 자연수를 더하여 return
4. 2~3번을 반복하며 모든 노드 탐색
5. 오름차순으로 정답을 추출해야 하기 때문에 정렬