[Programmers] 무인도 여행 JAVA

반응형

728x90

[Programmers] 무인도 여행 - LV 2

---

접근

• dfs

---

풀이

무인도 여행이라는 문제로 좌표가 주어지고 X 가 적혀있는 곳은 바다 숫자가 적혀있는 곳은 무인도로 숫자는 해당 땅에서 숫자 일수만큼 버틸 수 있는 식량이 존재한다는 뜻이다. 연결된 섬들에서 머무를 수 있는 일수를 모두 구한 뒤 배열에 담아 오름차순으로 반환하는 문제이다. 

 

유사한 문제를 많이 풀었기 때문에 제일 먼저 생각나는 bfs, dfs로 풀었다. 이 문제는 모든 위치를 탐색하기만 하면 되기 때문에 dfs, bfs 중 아무거나 사용해도 큰 상관이 없어 재귀를 이용한 dfs로 풀었다. LeetCode에서 문제를 풀다 보니 재귀로 해결한 코드와 큐나 스택을 직접 사용한 코드의 속도 차이를 보니 자연스럽게 재귀로 해결이 가능하다면 시도해 보는 것 같다. 

    private static final int[] dx = {0, 0, 1, -1};
    private static final int[] dy = {1, -1, 0, 0};

    public int[] solution(String[] maps) {
        List<Integer> ls = new ArrayList<>();
        boolean[][] isVisited = new boolean[maps.length][maps[0].length()];
        char[][] mapsArr = new char[maps.length][];

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

        for (int i = 0; i < mapsArr.length; i++) {
            for (int j = 0; j < mapsArr[i].length; j++) {
                if (!isVisited[i][j] && mapsArr[i][j] != 'X') {
                    ls.add(dfs(mapsArr, isVisited, i, j));
                }
            }
        }

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

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

우선 좌표가 문자열 배열로 주어지기 때문에 접근을 편하게 하기 위해 2차원 char 배열로 변환해 주었다. 그리고 좌표를 순회하며 해당 위치를 방문하지 않고 바다가 아닌 곳에서 dfs를 시작하고 값을 리스트에 담은 뒤 나중에 후처리를 해주었다.

    private int dfs(char[][] maps, boolean[][] isVisited, int x, int y) {
        if (x < 0 || x >= maps.length || y < 0 || y >= maps[x].length || isVisited[x][y] || maps[x][y] == 'X') {
            return 0;
        }

        isVisited[x][y] = true;
        int sum = maps[x][y] - '0';

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

            sum += dfs(maps, isVisited, nx, ny);
        }

        return sum;
    }

dfs 코드이다. 좌표 값이 올바르지 않다면 0을 반환하고 정상적인 섬의 좌표라면 방문처리 후 값들을 더하고 상하좌우로 탐색을 수행해 주게 된다. 

---

전체 코드

import java.util.*;

class Solution {
    private static final int[] dx = {0, 0, 1, -1};
    private static final int[] dy = {1, -1, 0, 0};

    public int[] solution(String[] maps) {
        List<Integer> ls = new ArrayList<>();
        boolean[][] isVisited = new boolean[maps.length][maps[0].length()];
        char[][] mapsArr = new char[maps.length][];

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

        for (int i = 0; i < mapsArr.length; i++) {
            for (int j = 0; j < mapsArr[i].length; j++) {
                if (!isVisited[i][j] && mapsArr[i][j] != 'X') {
                    ls.add(dfs(mapsArr, isVisited, i, j));
                }
            }
        }

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

        return ls.stream()
                .sorted()
                .mapToInt(Integer::intValue)
                .toArray();
    }
    
    private int dfs(char[][] maps, boolean[][] isVisited, int x, int y) {
        if (x < 0 || x >= maps.length || y < 0 || y >= maps[x].length || isVisited[x][y] || maps[x][y] == 'X') {
            return 0;
        }

        isVisited[x][y] = true;
        int sum = maps[x][y] - '0';

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

            sum += dfs(maps, isVisited, nx, ny);
        }

        return sum;
    }
}