Programmers - 무인도 여행 154540번

Programmers - 무인도 여행 154540번

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

 

제한사항 이 부담이 없으므로 전체탐색을 통해 한번 쫘악 훑어 주면 될거 같다.

Queue를 활용한 bfs(너비우선탐색) 을 이용하여 문제를 풀었다.

이때 point가 약간 혼란스러울 수 있는데, 내가 생각한 y좌표는 height 높이라고 생각했고,

x좌표는 width 너비를 생각하여 문제를 풀이했는데 point 에서 제공하는 y와 x는 그 반대여서

Queue에 add할때 반대로 넣은걸 볼 수 있는데, 다음엔 다른걸 사용하여 이런 귀찮은 일을 없애야 겠다.

그리고 보면 문제에 비해 소스가 이상하게 좀 긴 느낌인데 쓸때 없는 부분을 정리해서 다시 짜 봐야겠음

 

xxxxxxxxxx

import java.awt.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class Programmers_154540 {

    final int MAX_ISLAND_SIZE = 101;
    int[][] island = new int[MAX_ISLAND_SIZE][MAX_ISLAND_SIZE];
    int[][] check = new int[MAX_ISLAND_SIZE][MAX_ISLAND_SIZE];

    // 12시 부터 시계방향 검사
    int[] dir_y = {-1,0,1,0};
    int[] dir_x = {0,1,0,-1};

    public int[] solution(String[] maps) {
        ArrayList<Integer> res = new ArrayList<>();

        island = createIsland(maps);

        for(int i = 0; i < maps.length; i++) {
            for(int j = 0; j < maps[i].length(); j++) {

                if(island[i][j] != 0 && check[i][j] == 0) {
                    res.add(bfs(i, j));
                }
            }
        }

        if(res.size() == 0) {
            res.add(-1);

            return res.stream()
                    .mapToInt(Integer::intValue)
                    .toArray();
        }

        Collections.sort(res);

        return res.stream()
                .mapToInt(Integer::intValue)
                .toArray();
    }

    int bfs(int y, int x) {

        Queue<Point> q = new LinkedList<>();
        int result = 0;

        // 체크안한 땅이고, 섬이면 진행
        if(check[y][x] != 1 && island[y][x] != 0) {
            q.add(new Point(x,y));
            check[y][x] = 1;
            result += island[y][x];
        }

        while(q.size() != 0) {
            int island_y = q.peek().y;
            int island_x = q.poll().x;

            // 4방향 검사
            for(int i = 0; i < 4; i++) {
                int next_island_y = island_y + dir_y[i];
                int next_island_x = island_x + dir_x[i];

                if(next_island_y < 0 || next_island_x < 0)
                    continue;

                if(check[next_island_y][next_island_x] != 0)
                    continue;

                if(island[next_island_y][next_island_x] == 0)
                    continue;

                result += island[next_island_y][next_island_x];
                check[next_island_y][next_island_x] = 1;
                q.add(new Point(next_island_x, next_island_y));
            }
        }

        return result;
    }

    int[][] createIsland(String[] maps) {
        int[][] result = new int[MAX_ISLAND_SIZE][MAX_ISLAND_SIZE];

        for(int i = 0; i < maps.length; i++) {
            for(int j = 0; j < maps[i].length(); j++) {
                String tmp = maps[i].substring(j, j+1);
                if(tmp.equals("X"))
                    result[i][j] = 0;
                else
                    result[i][j] = Integer.parseInt(tmp);
            }
        }
        return result;
    }
}