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

1. 문제

무인도 여행

2. 개요

1x1 크기의 격자로 이루어진 무인도의 지도가 주어진다.

X는 바다를 나타내고 숫자는 땅을 의미하며, 상하좌우로 연결된 땅은 하나의 섬으로 간주한다.

각 섬의 숫자의 총 합은 해당 섬에서 버틸 수 있는 최대 일수를 의미한다.

각 섬에서 버틸 수 있는 최대 일수들을 정렬된 배열로 리턴하는 문제.

3. 풀이 및 코드

3-1. 풀이

지도의 가로, 세로 크기를 먼저 구해놓고, 방문처리할 visited배열도 미리 만들어둔다.

지도의 범위 내를 탐색하면서 해당 구역이 바다가 아닌 땅이라면 해당 구역을 방문처리하고 BFS를 수행한다.

BFS 내부에서는 큐를 만들어 시작점을 넣고 크기를 시작점의 값만큼 초기화한 후 시작한다.

반복문 내에서 큐의 맨 앞의 원소를 빼내어 상하좌우를 탐색하면서 지도의 범위 내의 아직 방문하지 않은 땅이라면 방문처리 후 사이즈를 해당 위치의 값 만큼 늘리고 큐에 넣는 작업을 반복한다. 큐가 모두 비었다면 반복문을 빠져나와 사이즈를 리턴한다.

BFS 수행으로 얻은 해당 섬의 크기를 리스트에 넣는다.

모든 탐색이 완료되었다면, 섬이 존재하지 않는 경우가 존재하므로 리스트의 크기가 0이라면 -1값을 넣어준다.

완성된 리스트를 정렬한 후 리스트를 배열로 변환해 리턴하면 끝.

3-2. C#

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

namespace Programmers_
{
    public class AloneinIsland
    {
        static bool[,] visited;
        static int len_y;
        static int len_x;

        static public int[] Solution(string[] maps)
        {
            List<int> answer = new List<int>();

            len_y = maps.Length;
            len_x = maps[0].Length;

            visited = new bool[len_y, len_x];

            for (int i = 0; i < len_y; i++)
            {
                for (int j = 0; j < len_x; j++)
                {
                    if (maps[i][j] == 'X')
                        continue;

                    if (visited[i, j])
                        continue;

                    visited[i, j] = true;
                    answer.Add(BFS(maps, i, j));
                }
            }

            if (answer.Count == 0)
                answer.Add(-1);

            answer.Sort();

            return answer.ToArray();
        }

        static public int BFS(string[] maps, int y, int x)
        {
            int size = int.Parse(maps[y][x].ToString());

            int[] dirY = { -1, 0, 1, 0 };
            int[] dirX = { 0, -1, 0, 1 };

            Queue<int[]> q = new Queue<int[]>();
            q.Enqueue(new int[] { y, x });

            while (q.Count > 0)
            {
                int[] now = q.Dequeue();
                int nowY = now[0];
                int nowX = now[1];

                for (int i = 0; i < 4; i++)
                {
                    int nextY = nowY + dirY[i];
                    int nextX = nowX + dirX[i];

                    if (nextY < 0 || nextY >= len_y || nextX < 0 || nextX >= len_x)
                        continue;

                    if (maps[nextY][nextX] == 'X')
                        continue;

                    if (visited[nextY, nextX])
                        continue;

                    int value = int.Parse(maps[nextY][nextX].ToString());
                    size += value;
                    visited[nextY, nextX] = true;
                    q.Enqueue(new int[] { nextY, nextX });
                }
            }

            return size;
        }
    }
}