[C#][프로그래머스] 무인도 여행

프로그래머스 > 코딩테스트 연습 > 연습문제 >  무인도 여행

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

 

📒 문제

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 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

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

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

• 이를 오름차순으로 정렬하면 [1, 1, 27]이 됩니다.

입출력 예 #2

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

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

---

💻 소스코드

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string[] maps) {
        string [,] m = new string[maps.Length, maps[0].Length];
        bool[,] visited = new bool[maps.Length, maps[0].Length];
        for (int i = 0; i < m.GetLength(0); i++)
        {
            for (int j = 0; j < m.GetLength(1); j++)
            {
                string str = maps[i][j].ToString();
                m[i, j] = str;
                if (str == "X")
                    visited[i, j] = true;
            }
        }
        
        List<int> answer = new List<int>();
        Stack<int[]> stack = new Stack<int[]>();
        
        // 0,0 부터 차례대로 확인
        for(int i = 0; i < m.GetLength(0); i++)
        {
            for(int j = 0; j < m.GetLength(1); j++)
            {
                if (visited[i, j]) continue;

                stack.Push(new int[]{i, j});
                visited[i, j] = true;

                int sum = 0;
                while (stack.Count > 0)
                {
                    int[] xy = stack.Pop(); // [x, y]
                    int x = xy[0];
                    int y = xy[1];

                    sum += int.Parse(m[x, y]);
                    visited[x, y] = true;

                    // 동
                    if (x+1 < m.GetLength(0))
                    {
                        if (!visited[x+1, y])
                        {
                            stack.Push(new int[] { x+1, y });
                            visited[x+1, y] = true;
                        }
                    }

                    // 서
                    if (x-1 >= 0)
                    {
                        if (!visited[x-1, y])
                        {
                            stack.Push(new int[] { x-1, y });
                            visited[x-1, y] = true;
                        }
                    }

                    // 남
                    if (y+1 < m.GetLength(1))
                    {
                        if (!visited[x, y+1])
                        {
                            stack.Push(new int[] { x, y+1 });
                            visited[x, y+1] = true;
                        }
                    }

                    // 북
                    if (y-1 >= 0)
                    {
                        if (!visited[x, y-1])
                        {
                            stack.Push(new int[] { x, y-1 });
                            visited[x, y-1] = true;
                        }
                    }
                }
                answer.Add(sum);
            }
        }
        answer.Sort();
        answer = answer.Count == 0 ? new List<int> { -1 } : answer;
        
        return answer.ToArray();
    }
}

 

📝 풀이

먼저 mpas를 옮길 string 2차원 배열 m과 확인 여부를 판단할 bool 2 차원 배열 visited를 선언하고, maps를 m으로 옮겨줬다.

그 과정에서 maps에 "X"로 표시된 부분은 visited에 해당 인덱스를 true로 표시해 "X"가 담긴 부분은 나중에 확인하지 않도록 해두었다.

 

이제 m을 0,0부터 차례대로 확인한다.

 

확인 중 숫자가 나오면 stack에 쌓아서 주위에 또 다른 숫자가 있는지 파악한다.

sum에 해당 좌표 숫자를 더하고 visited를 true로 바꿔준다,

동, 서, 남, 북이 숫자인지 확인하고 숫자면 해당 좌표를 stack에 쌓는다,

그 다음 stack에 다음 좌표를 꺼내서 위 내용을 반복한다.

 

stack에 아무것도 없으면 숫자 확인을 종료하고 sum을 answer에 추가하고 다음 좌표를 확인한다.

 

좌표 확인이 모두 끝나면 answer를 오름차순 array로 변경하고 return해준다. 이때 answer에 담겨있는게 없다면 -1이 담긴 array로 return한다. 

 

---

관련 포스팅

[알고리즘] 깊이 우선 탐색, DFS(Deep-First Search) 코드 구현

 

[자료구조] 스택 (Stack)