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

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

주어진 값을 가진 땅에 따라 이어져 있는 땅들의 값을 각각 하나로 더하는 문제

- 방문배열을 만들어 중복체크를 피하고 maps[y축][x축]으로 보고 품

- 섬을 발견하면 이어진 땅을 확인 ( 확인하는 좌표도 방문체크가 되어야 함 )

- 이어진 땅을 찾는 방법은 이어진 모든 방향을 이어서 체크해야 하므로 BFS로 찾음 

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] DFS(Depth First Search), BFS(Breadth First Search)

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public int[] solution(string[] maps)
        {
            List<int> list = new List<int>(); // answerList

            bool[,] boolArray = new bool[maps.Length, maps[0].Length]; // 방문배열

            // 같은 인덱스 값에 따라 4가지 방향을 나타내는 배열
            int[] dirX = new int[4] { 0, 0, 1, -1 };
            int[] dirY = new int[4] { 1, -1, 0, 0 };

            // 맵을 순회함 i = y축, j = x축
            for (int i = 0; i < maps.Length; i++)
            {
                for (int j = 0; j < maps[i].Length; j++)
                {
                    // 방문체크
                    if (boolArray[i, j]) continue;
                    boolArray[i, j] = true;

                    if (maps[i][j] == 'X') continue;

                    // 파악되지 않은 섬을 발견
                    var queue = new Queue<(int, int)>();
                    int total = (int)maps[i][j] - (int)'0'; // 식량들의 합
                    queue.Enqueue((i, j));

                    // 마치 BFS처럼 동작하여 이어져있는 섬의 식량을 찾음
                    while (queue.Count != 0)
                    {
                        (int y, int x) currPos = queue.Dequeue();

                        for (int k = 0; k < 4; k++)
                        {
                            int currPosX = currPos.x + dirX[k];
                            int currPosY = currPos.y + dirY[k];

                            // 주어진 맵 범위 벗어남 체크
                            if (currPosY < 0 || currPosX < 0 ||
                              currPosY >= maps.Length || currPosX >= maps[0].Length)
                                continue;

                            // 방문 체크
                            if (boolArray[currPosY, currPosX]) continue;
                            boolArray[currPosY, currPosX] = true;

                            // 이어진 식량을 찾음
                            if (maps[currPosY][currPosX] != 'X')
                            {
                                queue.Enqueue((currPosY, currPosX));
                                total += (int)maps[currPosY][currPosX] - (int)'0';
                            }
                        }
                    }
                    // 만약, 섬을 발견한 적이 있다면 list에 추가
                    if (total != 0)
                        list.Add(total);
                }
            }
            
            // 섬이 없다면 조건에 따라 -1을 리턴
            if (list.Count == 0)
                return new int[1] { -1 };
            
            // 오름차순으로 정렬하여 리턴
            list.Sort();
            return list.ToArray();
        }
    }