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

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

프로그래머스

 

무인도 여행 문제

각 연결된 섬의  식량합을 구하는 문제

 

#사용 알고리즘

너비 우선 탐색(BFS)

반응형

📌문제 접근 포인트

1. 각각의 땅을 찾아 값을 더할 수 있도록 구성해야한다. 이를 위해 BFS를 활용해보자.

2. 찾기 시작한 땅에서부터 탐색해가면서 식량의 합을 반환해주고, 방문지점을 기록해주자. 이후 탐색 부터는 방문한 땅에 대해서는 탐색하지 않도록 구성해주자.

3. 섬을 모두 찾은 후 오름차순 정렬해서 반환하면 성공

⚙ 내가 푼 정답 코드

import java.util.*;

class Solution {
    static public int n, m;
    static public int[] dy = {1,-1,0,0};
    static public int[] dx = {0,0,1,-1};
    static public int[][] visited;
    static public char[][] map;
    static class land{
        int y, x;
        public land (int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
    
    public static int find(int a, int b){
        Queue<land> queue = new LinkedList<land>();
        queue.offer(new land(a,b));
        visited[a][b] = 1;
        int food = (int) map[a][b] - '0';
        while(!queue.isEmpty()){
            land l = queue.poll();
            for (int i = 0 ; i< 4; i++){
                int ny = l.y + dy[i];
                int nx = l.x + dx[i];
                
                if (0 <= ny && ny < n && 0 <= nx && nx < m && visited[ny][nx] == 0 && map[ny][nx] != 'X'){
                    visited[ny][nx] = 1;
                    food += (int) map[ny][nx] - '0';
                    queue.add(new land(ny, nx));
                }
            }
        }
        return food;
    }
    
    public int[] solution(String[] maps) {
        n = maps.length;
        m = maps[0].length();
        visited = new int[n][m];
        map = new char[n][m];
        
        for (int i = 0 ; i< n; i++){
            for (int j = 0; j < m; j++){
                map[i][j] = maps[i].charAt(j);
            }
        }
        
        ArrayList <Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++){
            for (int j = 0; j< m; j++){
                if(map[i][j] != 'X' && visited[i][j] == 0){
                    result.add(find(i,j));
                }
            }
        }
        if (result.isEmpty()){
            result.add(-1);
        }
        Collections.sort(result);
        
        int[] answer = new int[result.size()];
        for(int i = 0 ; i < result.size(); i++){
            answer[i] = result.get(i);
        }
        return answer;
    }
}