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

 

문제 설명

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

 

이 문제를 보았을때 바로 DFS알고리즘을 떠올랐다 숫자가 있는 섬은 true로 체크 그리고 상하좌우에 0보다 큰 숫자가 있는지 체크를 한후 재귀함수로 계속 이어지는 방식으로 코드를 짜놨다.

 

그리고 이미 간 지역은 true로 되어있으니 체크를 이미 한상태로 끝날것이고 다 돌았으면 더해진 값을 List로 값을 할당

이걸 정렬을 한값을 answer 배열에다 할당을 해서 반환값으로 제출하였다.

 

코드를 보겠다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution {
     static int[,] island;
       
        static bool[,] islandcheck;
        static int addisland = 0;
        static int addanswer = 0;
        static bool check = false;
    
    public int[] solution(string[] maps)
     {
                int[] answer;
                List<int> list = new List<int>();
                island = new int[maps.Length + 2, maps[0].Count() + 2];
                islandcheck = new bool[maps.Length + 2, maps[0].Count() + 2];

                for (int i = 1; i < maps.Length + 1; i++)
                {
                    if (i - 1 == maps.Length)
                        break;

                    char[] muindo = maps[i - 1].ToCharArray();

                    for (int j = 1; j < maps[0].Count() + 1; j++)
                    {
                        if (muindo[j - 1] == 'X')
                        {
                            island[i, j] = 0;
                            continue;
                        }
                        island[i, j] = int.Parse(muindo[j - 1].ToString());
                    }

                }


               for (int i = 1; i < maps.Length + 1; i++)
                {
                    for (int j = 1; j < maps[0].Count() + 1; j++)
                    {
                        if (island[i, j] != 0 && islandcheck[i, j] == false)
                        {
                            Check(i, j);
                            check = true;
                            list.Add(addisland);
                            addanswer++;
                            addisland = 0;
                        }
                    }
                }

                if (check == false)
                {
                    return new int[] { -1 };
                }


                answer = list.OrderBy(x => x).ToArray();
        
                return answer;

               
            }
    public void Check(int i, int j)
        {
            if (islandcheck[i, j] == true)
            {
                return;
            }
            else
            {
                addisland += island[i, j];
                islandcheck[i, j] = true;
            }

            if (island[i - 1, j] != 0)
            {
                Check(i - 1, j);
            }
            if (island[i, j - 1] != 0)
            {
                Check(i, j - 1);
            }
            if (island[i + 1, j] != 0)
            {
                Check(i + 1, j);
            }
            if (island[i, j + 1] != 0)
            {
                Check(i, j + 1);
            }

        }
}

 

 

프로그래머스 문제는 백준 문제와 달리 메서드를 던져주면서 메서드 안에다 코드를 적어서 제출해야 정답을 체크해주는 방식이다.

이문제도 비쥬얼 스튜디오로는 금방풀었는데 이걸 프로그래머스식으로 옮길때 좀 애먹은 문제였다.