[Lv.2] 무인도 여행 [프로그래머스_코딩테스트] [BFS, Greedy]

🔍 문제 요약

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

프로그래머스

문제는 string 배열이 주어지고 한 단어가 해당 인덱스 지점의 음식 수치를 나타낸다. X는 음식이 없는 상태. 그런 상황에서 상하좌우에 붙어 있는 지점에 음식 수치의 합들을 구해서 answer 배열에 넣고 오름차순으로 정렬시키는 문제

 

🧠 나의 접근 방식과 시행착오

일단 생각보다 시간이 오래 걸리긴 했었다. (GPT에게 물어봤을 때 제한 시간을 약 40분을 잡고 있는 듯 하나 이래저래 생각하다 보니 1시간 정도가 걸린 해결 방법. 또 결과적으로 내가 푼 문제 방향이 틀리진 않은 듯 한데 테스트 케이스에서 실패가 다수 떠있어서 뭔가를 놓친 부분이 있었는 듯 싶다.) BFS + Greedy 문제라고 해서 추천 받은 상태이나 BFS 방식으로 해당 문제 접근을 안 했긴 하다. 먼저 내가 푼 방식의 코드를 아래와 같이 첨부.

using System;
using System.Collections.Generic;

public class Solution
{
    /// <summary>
    /// 맵의 각 지점
    /// </summary>
    public struct Point
    {
        public int X { get; set; }
        public int Y { get; set; }
        public int Food { get; set; }

        public Point(int x, int y, int food)
        {
            X = x;
            Y = y;
            Food = food;
        }

        /// <summary>
        /// 생활 불가 지점
        /// </summary>
        public bool DontLive => Food <= 0;
    }
    
    /// <summary>
    /// 무인도 여행
    /// https://school.programmers.co.kr/learn/courses/30/lessons/154540
    /// </summary>
    public int[] solution(string[] maps) {
        // 맵에서 상-하-좌-우로 갈 수 있는 곳들을 연결시켜서 숫자의 합을 내면 최대 식량
        // 연결된 거가 없으면 해당 지점의 값
        // 결과는 오름차순으로
        int heightSize = maps.Length;
        int rowSize = maps[0].Length;
        var points = new List<Point>(heightSize * rowSize);
        
        // 1. 일단 Node에 map 정보를 저장.
        for (int i = 0; i < maps.Length; i++)
        {
            for (int j = 0; j < maps[i].Length; j++)
            {
                var value = maps[i][j] == 'X' ? 0 : (maps[i][j] - '0');
                points.Add(new Point(j, i, value));
            }
        }
        
        // 2. 주변 노드들을 하나의 묶음인지 체크. (이 부분이 핵심)
        // - 상하좌우 모두 체크 필요
        // - x,y 좌표 값을 하나로 합해서 pIndex로 계산하고, 리스트 같은 곳에 넣고 묶음으로 묶어야 함
        var indexSetList = new List<List<int>>();

        foreach (var point in points)
        {
            // 음식 없는 포인트
            if (point.DontLive) continue;
            
            // 위와 왼쪽에 있는 것들이 이미 들어가 있어서 연결 가능한지 체크
            // (오른쪽과 아래쪽은 반복분 순환 구조상 먼저 들어갈 수가 없는 구조)
            // (제일 윗 줄과 제일 왼쪽 줄일 때는 체크가 의미가 없음
            bool hasUpPoint = point.Y > 0;
            bool hasLeftPoint = point.X > 0;
            
            // 현재 위치 좌표 인덱스 값
            int curIndexVal = point.X + (point.Y * rowSize);

            // 왼쪽과 위로 연결된 인덱스 리스트
            List<int> connectedIndexList = null;

            if (hasLeftPoint)
            {
                connectedIndexList = indexSetList.Find(list => list.Contains(point.X - 1 + (point.Y * rowSize)));
            }
            
            if (connectedIndexList == null && hasUpPoint)
            {
                connectedIndexList = indexSetList.Find(list => list.Contains(point.X + ((point.Y - 1) * rowSize)));
            }
            
            // 묶을 수 있는 경우
            if (connectedIndexList != null)
            {
                connectedIndexList.Add(curIndexVal);
            }
            // 왼쪽, 위로 연결된 지점이 없음. 새로 리스트 만들어서 넣음
            else
            {
                indexSetList.Add(new List<int> { curIndexVal });
            }
        }

        // 하나도 없는 경우
        if (indexSetList.Count <= 0) return new[] { -1 };
        
        int[] answer = new int[indexSetList.Count];

        for (int i = 0; i < indexSetList.Count; i++)
        {
            var indexList = indexSetList[i];
            int foodSum = 0;

            foreach (var indexVal in indexList)
            {
                int xIndex = indexVal % rowSize;
                int yIndex = indexVal / rowSize;

                var pointData = points.Find((p) => p.X == xIndex && p.Y == yIndex);

                foodSum += pointData.Food;
            }

            answer[i] = foodSum;
        }
        
        // 오름 차순 정렬
        Array.Sort(answer);
        
        return answer;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var maps = new []{"1111", "1XX1", "1XX1", "1111"};
        var result = sl.solution(maps);
        
        foreach (var map in result)
        {
            Console.Write(map + ", ");
        }
    }
}

 

생각했던건 maps의 데이터를 Point라는 구조체를 만들어서 일단 집어 넣고 리스트화시킨 다음, 해당 리스트를 순회하면서 위 쪽과 왼쪽에 있는 지점에 이미 Point가 들어가 있는지 계산하는 방향이었다. 그렇게 해서 입출력 예제로 주어진 아래의 예시는 제대로 동작하는 것까지 확인은 완료된 상태. 실제로도 문제를 생각했을 때 다양한 테스트 케이스를 생각하지 못했던 것인지 왜 틀렸다고 나오는지, 틀린 테스트 케이스가 어떤 것인지 좀 고민을 해보았다. (이 뒤부터는 GPT에게 물어보면서 찾아보는 과정을 거쳐봄)

 

일단 그렇게 GPT를 돌린 결과 내가 너무 쉽게 생각했던 것을 판단...

좌에서 우로, 위에서 아래로 순차적으로 돌리기 때문에 필연적으로 위와 같은 테스트 케이스에서 문제가 발생하는 것을 이해하였다. (x = 1, y = 1을 돌 때 왼쪽과 오른 쪽에 아무 것도 없어서 묶음 처리를 못함..) 간단하게 리스트 구조로 해서 순차적으로 돌리는게 결국 불가능한 해결책임을 깨닫고 원칙적인 해결 방향이었던 BFS 방향으로 문제 풀이를 선회하기로 하였다. (추가로 내가 생각했던 방향에서는 List의 Find, Contains가 빈번히 돌기 때문에 효율에도 좋지 못한 점이 있다)

 

✅ 풀이 코드 

- BFS

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string[] maps) {
        int n = maps.Length;
        int m = maps[0].Length;
        bool[,] visited = new bool[n, m];
        List<int> foodList = new List<int>();

        int[] dx = { -1, 1, 0, 0 };
        int[] dy = { 0, 0, -1, 1 };

        for (int y = 0; y < n; y++) {
            for (int x = 0; x < m; x++) {
                if (maps[y][x] == 'X' || visited[y, x]) continue;

                int sum = 0;
                Queue<(int x, int y)> q = new Queue<(int x, int y)>();
                q.Enqueue((x, y));
                visited[y, x] = true;

                while (q.Count > 0) {
                    var (cx, cy) = q.Dequeue();
                    sum += maps[cy][cx] - '0';

                    for (int dir = 0; dir < 4; dir++) {
                        int nx = cx + dx[dir];
                        int ny = cy + dy[dir];

                        if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
                            if (!visited[ny, nx] && maps[ny][nx] != 'X') {
                                visited[ny, nx] = true;
                                q.Enqueue((nx, ny));
                            }
                        }
                    }
                }

                foodList.Add(sum);
            }
        }

        if (foodList.Count == 0) return new int[] { -1 };

        foodList.Sort();
        return foodList.ToArray();
    }
}

 

- DFS

using System;
using System.Collections.Generic;

public class Solution {
    private bool[,] visited;
    private int n, m;
    private string[] maps;
    private int[] dx = { -1, 1, 0, 0 };
    private int[] dy = { 0, 0, -1, 1 };

    public int[] solution(string[] maps) {
        this.maps = maps;
        n = maps.Length;
        m = maps[0].Length;
        visited = new bool[n, m];
        List<int> result = new List<int>();

        for (int y = 0; y < n; y++) {
            for (int x = 0; x < m; x++) {
                if (!visited[y, x] && maps[y][x] != 'X') {
                    int foodSum = DFS(x, y);
                    result.Add(foodSum);
                }
            }
        }

        if (result.Count == 0) return new int[] { -1 };

        result.Sort();
        return result.ToArray();
    }

    private int DFS(int x, int y) {
        visited[y, x] = true;
        int sum = maps[y][x] - '0';

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
                if (!visited[ny, nx] && maps[ny][nx] != 'X') {
                    sum += DFS(nx, ny); // 재귀로 연결된 지역 탐색
                }
            }
        }

        return sum;
    }
}

 

- Union-Find (Disjoint Set)

using System;
using System.Collections.Generic;

public class Solution
{
    int[] parent;
    int[] rank;
    int[] food;

    public int[] solution(string[] maps)
    {
        int n = maps.Length;
        int m = maps[0].Length;
        int size = n * m;

        parent = new int[size];
        rank = new int[size];
        food = new int[size];

        for (int i = 0; i < size; i++) parent[i] = i;

        for (int y = 0; y < n; y++)
        {
            for (int x = 0; x < m; x++)
            {
                int index = y * m + x;
                if (maps[y][x] == 'X') continue;

                food[index] = maps[y][x] - '0';

                // 좌
                if (x > 0 && maps[y][x - 1] != 'X')
                    Union(index, y * m + (x - 1));
                // 상
                if (y > 0 && maps[y - 1][x] != 'X')
                    Union(index, (y - 1) * m + x);
            }
        }

        // 섬별 식량 합산
        Dictionary<int, int> groupSum = new Dictionary<int, int>();
        for (int i = 0; i < size; i++)
        {
            if (food[i] == 0) continue;

            int root = Find(i);
            if (!groupSum.ContainsKey(root))
                groupSum[root] = 0;
            groupSum[root] += food[i];
        }

        if (groupSum.Count == 0) return new int[] { -1 };

        var result = new List<int>(groupSum.Values);
        result.Sort();
        return result.ToArray();
    }

    int Find(int x)
    {
        if (parent[x] != x)
            parent[x] = Find(parent[x]);
        return parent[x];
    }

    void Union(int x, int y)
    {
        int rx = Find(x);
        int ry = Find(y);
        if (rx == ry) return;

        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else
        {
            parent[ry] = rx;
            if (rank[rx] == rank[ry]) rank[rx]++;
        }
    }
}

 

🔄 정리

해당 문제를 풀이시 접근 방향에는 BFS, DFS, Union-Find등의 방향이 존재한다. 풀이를 통해 일단 BFS로 풀이를 이해하는게 좀 더 쉽게 이해가 가는 듯 하다. 특히 DFS의 경우 재귀를 써서 들어가다 보니 실제 개발에서는 이해하기도 좋지 못하고, 문제와 최적화 등에서 좋지 않은 해결책으로 보인다.

 

하단은 gpt에게 각 방식을 비교했을 때의 차이점을 정리해두었으니 참고하면 좋을 듯 하다.

	BFS	DFS	Union-Find
기본 개념	큐를 사용하여 넓이 우선 탐색	재귀 호출을 사용한 깊이 우선 탐색	각 좌표를 disjoint set으로 묶음
메모리 안정성	✅ 안정적 (재귀 없이 Queue 사용)	❌ 깊은 재귀로 StackOverflow 위험	✅ 안정적 (반복 기반 구현)
가독성	✅ 직관적, 흐름 따라가기 쉬움	❌ 로직 추적 어려움	❌ 추상적, 로직 이해에 학습 필요
성능	✅ 실전 충분	✅ 실전 충분	✅ 빠름 (큰 입력에서 효율적)
코드 길이	약간 길지만 명확	짧지만 이해 어려움	중간 (초기화 코드 많음)
디버깅 난이도	✅ 상태 확인 용이	❌ 재귀 흐름 추적 어려움	❌ parent 배열 추적 필요
게임개발 친화도	✅ ✅ 현업에서도 많이 사용함	❌ 드물게 사용 (AI에서 제한적으로)	⭕ 구조 파악되면 네트워크, 접속자 그룹 등 활용 가능

 

✅ 사용 우선순위 제안

⭐ 1순위	BFS	일반 연결 영역 탐색 (게임/알고리즘/디버깅)
⭐ 2순위	Union-Find	서로소 집합 관리, 성능 중심, 병합 필수 상황
🔸 3순위	DFS	입력 크기가 작고, 구조가 단순하며 빠른 구현이 필요할 때만 고려

 

추가로 BFS에 대해서 좀 더 정리

 

• 재귀 스택 오버플로우 리스크 없음
  • Unity, Unreal, 서버 등 콜스택이 제한된 환경에서는 안전이 우선
• 흐름이 명확해서 유지보수/디버깅에 유리
  • 큐로 탐색 순서가 눈에 보이고, 게임 디버깅 툴에서도 쉽게 추적 가능
• 연결 영역 탐색 로직의 기본기
  • Level Design, Flood Fill, Pathfinding 디버그에 가장 자주 쓰임
• 성능도 충분히 우수
  • 문제의 맵 크기가 작고, 섬 수가 많지 않기 때문에 부담 없음

🎮 실무 예시에서 BFS 쓰이는 곳

• 2D/3D 타일 기반 영역 확산 (Flood Fill)
• 네트워크 접속 상태 전파 시뮬레이션
• AI 경로 수색 로직 (A*나 BFS 기반 필터링용)
• LevelEditor에서 타일 확장 범위 확인