C# 무인도 여행 - DFS BFS 길찾기 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/154540

 

 

나의 코드

public int[] solution(string[] maps) 
{
    int width = maps[0].Length;
    int height = maps.Length;

    var answer = new List<int>();
    var closed = new HashSet<(int, int)>();

    for(int iy = 0; iy < height; ++iy)
    {
        for(int ix = 0; ix < width; ++ix)
        {
            (int y, int x) cur = (iy, ix);
            if(maps[iy][ix] == 'X') 
            {
                closed.Add(cur);
                continue;
            }

            if(closed.Contains(cur)) continue;

            // 집합에 속하지 않은 숫자를 발견함
            int food = 0;

            var openStack = new Stack<(int, int)>();
            openStack.Push(cur);
            closed.Add(cur);

            while(openStack.Count > 0)
            {
                (int y, int x) open = openStack.Pop();
                food += (maps[open.y][open.x] - '0'); // char형이라 숫자변환 후 식량값 더함

                var pointList = new List<(int, int)>();
                if(open.x > 0)          pointList.Add((open.y, open.x - 1));
                if(open.x < width - 1)  pointList.Add((open.y, open.x + 1));
                if(open.y > 0)          pointList.Add((open.y - 1, open.x));
                if(open.y < height - 1) pointList.Add((open.y + 1, open.x));

                foreach((int y, int x) point in pointList)
                {
                    if(closed.Contains(point)) continue;
                    if(maps[point.y][point.x] == 'X') continue;

                    openStack.Push(point);
                    closed.Add(point);
                }
            }

            answer.Add(food);
        } 
    }

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

    return answer.OrderBy(o => o).ToArray();
}

역시 평범한 길찾기 문제.

경로를 탐색하는게 아니기 때문에 BFS, DFS 어느쪽이든 상관없다.