🔥[99클럽 코테 스터디] 32일차 TIL - 무인도 여행

⏳문제

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

🚨제한 사항

• 3 ≤ maps의 길이 ≤ 100
• 3 ≤ maps[i]의 길이 ≤ 100
• maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
• 지도는 직사각형 형태입니다.

📄입출력 예

maps	result
["X591X","X1X5X","X231X", "1XXX1"]	[1, 1, 27]
["XXX","XXX","XXX"]	[-1]

입출력 예 #1

위 문자열은 다음과 같은 지도를 나타냅니다.

연결된 땅들의 값을 합치면 다음과 같으며

입출력 예 #2

위 문자열은 다음과 같은 지도를 나타냅니다.

섬이 존재하지 않기 때문에 -1을 배열에 담아 반환합니다.

---

✏️풀이

이 문제를 보자마자 저번에 풀었던 단지 번호 붙이기 문제가 생각이 나서 dfs로 풀어야 겠다는 생각이 들었다.🤔

마찬가지로, 2차원 배열에 지도를 저장해 인덱스를 쭉 순회 하다가,
땅을 발견하면, 해당 위치를 기준으로 상하좌우를 살핀 뒤, 연속된 땅으로 이동하는 것을 반복해 주면 된다.

여기서 단지 번호 붙이기 문제와 다른 점은, 연속된 땅의 개수를 세는 것이 아니라, 해당 땅의 생존 일수 정보를 더해나가며 무인도의 최종 생존 일수를 구해야 한다는 것이다.

구현에 있어서는 int형 변수를 하나 만들어 연속된 땅의 위치로 옮겨갈 때마다 해당 위치의 원소값을 더해나가는 로직만 추가해 주면 된다.

🌱나의 코드

import java.util.*;

class Solution {
    static int[][] map; // 지도
    static boolean[][] visited; // 방문 여부
    static int dayCount; // 해당 땅에서의 생존 일수
    static int[][] step = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 상하좌우 이동
    static int sizeRow; // 지도 가로 크기
    static int sizeCol; // 지도 세로 크기

    public static int[] solution(String[] maps) {
        int[] answer;
        sizeRow = maps[0].length();
        sizeCol = maps.length;
        map = new int[sizeCol][sizeRow];
        visited = new boolean[sizeCol][sizeRow];
        ArrayList<Integer> days = new ArrayList<>(); // 무인도에서의 총 생존 일수

        // 지도 정보 입력
        for (int i = 0; i < sizeCol; i++) {
            String temp = maps[i];
            for (int j = 0; j < sizeRow; j++) {
                if (temp.charAt(j) == 'X') {
                    map[i][j] = 0;
                }
                else {
                    map[i][j] = Integer.parseInt(Character.toString(temp.charAt(j)));
                }
            }
        }


        for (int i = 0; i < sizeCol; i++) {
            for (int j = 0; j < sizeRow; j++) {
                if (!visited[i][j] && map[i][j] != 0) {
                    dayCount = 0;
                    dfs(i, j); // dfs 호출
                    days.add(dayCount); // 총 생존 일수 저장
                }
            }
        }

        // 찾은 무인도가 없다면 -1 저장
        if (days.isEmpty()) {
            answer = new int[1];
            answer[0] = -1;
        }
        
        // 찾은 무인도가 있다면 오름차순으로 생존 일수 저장
        else {
            answer = new int[days.size()];

            for (int i = 0; i < answer.length; i++) {
                answer[i] = days.get(i);
            }
            Arrays.sort(answer);
        }

        return answer;
    }

    public static void dfs(int a, int b) {
        visited[a][b] = true; // 방문 여부 표시
        dayCount += map[a][b]; // 생존 일수 증가

        // 상하좌우 탐색
        for (int i = 0; i < 4; i++) {
            // 이동한 좌표 갱신
            int newX = a + step[i][0];
            int newY = b + step[i][1];

            // 이동한 좌표가 지도 안에 있고, 땅이 이어져 있고, 아직 방문하지 않은 곳이라면
            if (newX >= 0 && newX < sizeCol && newY >= 0 && newY < sizeRow && map[newX][newY] != 0 && !visited[newX][newY]) {
                dfs(newX, newY); // 해당 좌표로 이동
            }
        }

        
    }
}

🌱코드 설명

1. 지도의 가로, 세로 크기를 구해준 뒤, 해당 크기와 일치하는 2차원 배열 map을 생성해주고, maps배열 중 "X"를 제외한 숫자만 지도에 저장한다.

2. map[0][0]부터 지도의 끝까지 순회하면서, 방문한 적이 없고, 요소가 0이 아닌 위치에서 dfs를 호출한다. 이 때, 해당 무인도의 총 생존 일수를 저장하는 dayCount를 0으로 초기화 한다.

3. 해당 땅의 방문 여부를 표시하고, 총 생존 일수를 해당 땅의 생존 일수만큼 증가시킨다.

4. 상하좌우 이동 정보를 저장한 2차원 배열 step 을 이용해 좌표를 갱신한다.

5. 이동한 좌표가 지도 안에 있고, 땅이 이어져 있고, 아직 방문하지 않은 곳이라면, 해당 좌표로 이동해 dfs를 재귀 호출한다.

6. 지도 탐색이 끝나면, 찾은 무인도의 총 일수를 저장하는 days를 확인해, 찾은 무인도가 없다면 answer에 -1을 저장하고, 찾은 무인도가 있다면 생존 일수들을 answer에 오름차순으로 저장한다.

---

🔗문제 링크
💻Repository