154540. 무인도 여행

문제

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

프로그래머스

제한사항

풀이

import java.util.*;

class Solution {
    public int[] solution(String[] maps) {
        int[] answer = {};
        List<Integer> result = new ArrayList<>();
        int n = maps.length;
        int m = maps[0].length();
        
        int[][] mapArr =new int [n][m];
        boolean[][] visited = new boolean[n][m];
        
        for(int i = 0 ; i< n;i++) 
            for(int j = 0 ; j<m ; j++) {
                if(maps[i].charAt(j) != 'X') {
                    mapArr[i][j] = maps[i].charAt(j) - '0';
                } else {
                    mapArr[i][j] = 0;
                }
                // System.out.println(mapArr[i][j]);
            }
        
        for(int i = 0 ; i< n;i++) 
            for(int j = 0 ; j<m ; j++) {
                if(visited[i][j] || mapArr[i][j] == 0) continue;
                
                int days = bfs(i, j, visited, mapArr);
                result.add(days);
                // String arr[] = arrList.toArray(new String[arrListSize]);
            }
        if(result.isEmpty()) return new int[]{-1};
        answer = result.stream().mapToInt(i->i).toArray();
        Arrays.sort(answer);
        return answer; 
        
    }
    
    int bfs(int r, int c, boolean[][] visited, int[][] mapArr) {
        
        Queue<int[]> q = new LinkedList<>();
        int n = mapArr.length;
        int m = mapArr[0].length;
        
        int[][] dir = {{-1,0}, {1, 0}, {0, -1}, {0, 1}};
        int days = mapArr[r][c];
        q.offer(new int[]{r, c});
        visited[r][c] = true;
        
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            
            for(int i = 0 ; i < 4 ; i++) {
                int nr = cur[0] + dir[i][0];
                int nc = cur[1] + dir[i][1];
                
                if(nr>=0 && nr < n && nc>=0 && nc<m && !visited[nr][nc] && mapArr[nr][nc]!=0) {
                    q.offer(new int[]{nr, nc});
                    visited[nr][nc] = true;
                    // System.out.println("mapArr[nr][nc]: " + mapArr[nr][nc]);            
                    days+= mapArr[nr][nc];
                }
            }
        }
        // System.out.println("days: " + days);
        return days;
    }
}

회고

섬을 찾고 섬에 머물 수 있는 기한을 찾는 문제였다. 기한은 섬을 구성하는 좌표의 값을 합한 값이다. BFS를 이용해 섬을 탐색하는 작업을 하였다. 비교적 쉬운 문제였지만, 각 좌표의 방문 또는 '섬'을 확인할 때, 섬일 경우 첫 방문 좌표를 방문 체크하지 않아서 살짝 헤맸다.