99클럽 코테 스터디 32일차 TIL , 무인도 여행

문제

풀이

String 배열에 지도를 담아서 입력된다. 지도에서 X는 바다고 숫자는 하루 먹을 식량이어서 식량만큼 무인도에서 버틸 수가 있다. 무인도는 위아래좌우로 묶여있다. 각 무인도에서 버틸 수 있는 일 수를 오름차순으로 정렬해서 나타낸다. 만약 무인도가 없다면 -1을 담아 출력한다.

제출 1 - 정답

import java.util.*;
class Solution {
    public int[] solution(String[] maps) {
        List<Integer> count = new ArrayList<>();
        char[][] map = new char[maps.length][];
        int idx = 0;
        for(String str : maps){//char배열에 maps들을 담아줌
            char[] chrArr= str.toCharArray();
            map[idx++] = chrArr;
        }

        //이동 방향
        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};

        for(int i=0;i<maps.length;i++){
            for(int j=0;j<maps[0].length();j++){
                if(map[i][j] == 'X') continue;  //X(바다) 면 통과
                Deque<int[]> que = new ArrayDeque<>();
                int cnt = map[i][j] - '0';	//발견된 값 담아주고
                map[i][j] = 'X';	//값 담고 X로 바꿔주고
                que.offer(new int[]{i, j});	//큐에 좌표 넣어준다.

                while(!que.isEmpty()){	//큐가 빌 때까지(이어져 있는 무인도 확인)
                    int[] val = que.poll();
                    for(int k=0;k<4;k++){
                        int nx = val[0] + dx[k];
                        int ny = val[1] + dy[k];
                        if(nx >= 0 && ny >= 0 && nx < maps.length && ny < maps[0].length() && map[nx][ny] != 'X'){
                            que.offer(new int[]{nx,ny});
                            cnt += map[nx][ny] - '0';
                            map[nx][ny] = 'X';
                        }
                    }
                }

                count.add(cnt);
            }
        }
        int[] answer;
        if(count.size() == 0){	//무인도가 없으면 -1 담아서 반환
            answer = new int[]{-1};
        }else{	//있으면 오름차순 정렬
            answer = new int[count.size()];
            for(int i=0;i<count.size();i++){
                answer[i] = count.get(i);
            }
            Arrays.sort(answer);
        }


        return answer;
    }
}

 

BFS로 풀이 했다.

발견되면 그 기준으로 무인도를 전부 발견해서 계산해주고 담아둔다.

자세한 설명은 코드에 주석으로 달아놨다.

TIL

• 조건문이나 반복문의 조건을 잘 설정하자