99클럽 코테 스터디 32일차 TIL - [프로그래머스] 무인도 여행(Java)

📌 오늘의 학습 키워드

[프로그래머스] 무인도 여행 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/154540

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 지도를 나타내는 문자열 배열 maps[] (3 ≤ maps.length ≤ 100)
출력 : 각 섬에서 최대 머무를 수 있는 정수 배열 result[]. 단, 지낼 수 있는 무인도가 없다면 -1 리턴

가능한 시간복잡도

O(n)

알고리즘 선택

dfs

📌 코드 설계하기

1. n, m, visited, maps, islands를 초기화한다.
2. 맵의 모든 위치를 순회한다. 만약 해당 위치가 방문되지 않았고, 바다가 아니면 DFS를 사용해 해당 섬의 크기를 계산하고 islands 리스트에 추가한다.
3. dfs에서는 현재 위치를 방문한 것으로 표기하고, 현재 위치의 숫자를 sum에 더한다.
4. 네 방향(상하좌우)에 대해 다음 위치(nx, ny)가 맵 범위 내에 있고, 방문하지 않았으며, 바다가 아니면 재귀적으로 dfs를 호출하여 섬의 크기를 계속 합산한다.
5. 모든 연결된 땅을 탐색 후 최종 합산된 섬의 크기를 반환한다.
6. 섬이 없으면 -1을 반환하고, 섬이 있으면 섬의 크기를 오름차순 정렬 후 배열로 변환해 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

class Solution {
    private int n, m; //맵의 행과 열의 크기
    private boolean[][] visited;
    private String[] maps; //입력으로 받은 맵을 저장
    private int[] dx = {0, 0, -1, 1};
    private int[] dy = {-1, 1, 0, 0};

    public int[] solution(String[] maps) {
        this.n = maps.length;
        this.m = maps[0].length();
        this.visited = new boolean[n][m];
        this.maps = maps;
        List<Integer> islands = new ArrayList<>(); //섬의 크기를 저장할 리스트

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && maps[i].charAt(j) != 'X') {
                    islands.add(dfs(i, j));
                }
            }
        }

        if (islands.isEmpty()) {
            return new int[]{-1};
        }

        Collections.sort(islands);
        return islands.stream().mapToInt(i -> i).toArray();
    }

    private int dfs(int x, int y) {
        visited[x][y] = true;
        int sum = maps[x].charAt(y) - '0'; //현재 위치에 있는 문자를 숫자로 변환

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx >= 0 && ny >= 0 && nx < n && ny < m && !visited[nx][ny] && maps[nx].charAt(ny) != 'X') {
                sum += dfs(nx, ny);
            }
        }

        return sum;
    }
}