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

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

프로그래머스

 

접근 방법

1. maps가 100 x 100의 2차원 격자이므로 일반적인 그래프 탐색을 해도 되는 입력 범위이다.
2. 격자를 탐색하며 X이거나 방문했으면 넘어간다.
3. 아니면 bfs/dfs를 진행한다.
4. 탐색을 진행하며 vis배열에 방문기록을 남긴다. 식량의 합을 구하고, 리스트 ans에 합을 추가한다
5. 리스트를 정렬하고 배열로 바꿔 반환한다.

코드 (BFS)

import java.util.*;
class Solution {
    int n,m;
    int[] dr = {-1,1,0,0}, dc={0,0,-1,1};
    boolean[][] vis;
    List<Integer> ans = new ArrayList<>();
    public int[] solution(String[] maps) {
        n = maps.length;
        m = maps[0].length();
        vis = new boolean[n][m];
        
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                if(vis[i][j] || maps[i].charAt(j) == 'X') continue;
                bfs(i,j,maps);
            }
        }
        
        if(ans.isEmpty()) return new int[]{-1};
        return ans.stream().mapToInt(Integer::intValue).sorted().toArray();
    }
    void bfs(int r,int c, String[] maps){
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{r,c});
        vis[r][c] = true;
        
        int sum = 0;
        while(!q.isEmpty()){
            int[] cur = q.poll();
            sum += maps[cur[0]].charAt(cur[1])-'0';
            for(int i = 0 ; i <4 ; i++){
                int nr = cur[0] + dr[i];
                int nc = cur[1] + dc[i];
                
                if(OOB(nr,nc) || maps[nr].charAt(nc) == 'X' || vis[nr][nc]) continue;
                q.offer(new int[]{nr,nc});
                vis[nr][nc] = true;
            }
        }
        
        ans.add(sum);
    }
    boolean OOB(int r,int c){
        return r < 0 || r >= n || c < 0 || c >= m;
    }
}

 

코드(DFS)

import java.util.*;
class Solution {
    int n,m,value;
    int[] dr = {-1,1,0,0}, dc={0,0,-1,1};
    boolean[][] vis;
    List<Integer> ans = new ArrayList<>();
    public int[] solution(String[] maps) {
        n = maps.length;
        m = maps[0].length();
        vis = new boolean[n][m];
        
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                if(vis[i][j] || maps[i].charAt(j) == 'X') continue;
                dfs(i,j,maps);
                ans.add(value);
                value = 0;
            }
        }
        
        if(ans.isEmpty()) return new int[]{-1};
        return ans.stream().mapToInt(Integer::intValue).sorted().toArray();
    }
    void dfs(int r,int c, String[] maps){
        vis[r][c] = true;
        
        value+=maps[r].charAt(c)-'0';
            
        for(int i = 0 ; i <4 ; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];

            if(OOB(nr,nc) || maps[nr].charAt(nc) == 'X' || vis[nr][nc]) continue;
            dfs(nr,nc,maps);
        }
    }
    boolean OOB(int r,int c){
        return r < 0 || r >= n || c < 0 || c >= m;
    }
}