[JAVA 문제 풀이] 382. 무인도 여행

내가 작성한 코드 (BFS)

import java.util.*;

class Solution {
    public int[] solution(String[] maps) {
        int n = maps.length;
        int m = maps[0].length();
        char[][] cMap = new char[n][m];

        // 문자열 배열을 문자 배열로 변환
        for (int i = 0; i < n; i++) {
            cMap[i] = maps[i].toCharArray();
        }

        boolean[][] visited = new boolean[n][m]; // 방문 여부 체크
        List<Integer> travelDistances = new ArrayList<>(); // 무인도에서의 거리 합산을 위한 리스트

        // 모든 위치에서 BFS 수행
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (cMap[i][j] != 'X' && !visited[i][j]) {
                    int distance = bfs(i, j, cMap, visited);
                    travelDistances.add(distance);
                }
            }
        }

        if (travelDistances.isEmpty()) {
            return new int[]{-1}; // 무인도가 없는 경우
        }

        // 정렬 후 배열로 변환
        Collections.sort(travelDistances);
        return travelDistances.stream().mapToInt(Integer::intValue).toArray();
    }

    // BFS 방식으로 무인도 탐색 및 거리 합산
    private int bfs(int x, int y, char[][] map, boolean[][] visited) {
        // 상하좌우
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        int n = map.length; // 행의 개수
        int m = map[0].length; // 열의 개수
        int sum = 0;

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y}); // 시작 위치를 큐에 추가
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cx = cur[0];
            int cy = cur[1];

            // 현재 위치의 거리 합산
            sum += map[cx][cy] - '0';

            // 4방향 탐색
            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                // 범위 체크 및 조건 확인
                if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    if (!visited[nx][ny] && map[nx][ny] != 'X') {
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }

        return sum;
    }
}

다른 사람의 코드 (DFS)

import java.util.*;

class Solution {
    // 상하좌우 방향 이동을 위한 배열
    int[] dx = { -1, 1, 0, 0 };
    int[] dy = { 0, 0, -1, 1 };

    int rows; // 행의 개수
    int cols; // 열의 개수
    boolean[][] visited; // 방문 여부를 저장하는 배열
    char[][] map; // 입력된 맵을 저장하는 2차원 문자 배열

    public int[] solution(String[] maps) {
        rows = maps.length;
        cols = maps[0].length();
        map = new char[rows][cols];
        visited = new boolean[rows][cols];

        // 입력된 문자열 배열을 문자 배열로 변환
        for (int i = 0; i < rows; i++) {
            map[i] = maps[i].toCharArray();
        }

        List<Integer> result = new ArrayList<>(); // 결과를 저장할 리스트

        // 모든 좌표에 대해 DFS 수행
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 방문하지 않았고, 'X'가 아닌 숫자인 경우
                if (!visited[i][j] && map[i][j] != 'X') {
                    int sum = dfs(i, j); // 연결된 영역의 숫자 합
                    result.add(sum); // 결과 리스트에 추가
                }
            }
        }

        // 유효한 영역이 없으면 -1 반환
        if (result.isEmpty()) {
            return new int[] { -1 };
        }

        // 오름차순 정렬 후 배열로 변환
        Collections.sort(result);
        return result.stream().mapToInt(Integer::intValue).toArray();
    }

    // DFS 탐색 함수
    private int dfs(int x, int y) {
        visited[x][y] = true;
        int sum = map[x][y] - '0'; // 현재 위치 숫자를 정수로 변환하여 더함

        for (int dir = 0; dir < 4; dir++) {
            // 상하좌우로 이동
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            // 배열 범위 체크 + 방문 여부 + 'X' 여부
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
                if (!visited[nx][ny] && map[nx][ny] != 'X') {
                    sum += dfs(nx, ny); // 재귀적으로 주변 영역 탐색
                }
            }
        }

        return sum;
    }
}