[Lv.2] 네트워크 [프로그래머스_코딩테스트] [DFS, 그래프] [25분]

🔍 문제 요약

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

프로그래머스

 

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

시간을 정말 오래 잡아 먹은 문제 한 60분 걸린 듯 하다. 아무래도 아직 익숙치 않던 graph와 DFS가 섞인 문제라 그런지 속도가 풀이에 있어서 속도가 잘 나지 않았던 듯 하다. 하긴 애초에 해당 문제 유형들은 시간보다 제대로 푸는 거에 좀 더 초점을 맞춰서 풀려고 시도했긴 하다. 필자의 풀이 방식은 일단 특정 인덱스 노드에서 다른 인덱스 노드로 연결된 경우 이중 리스트 graph에 넣는다. 그리고 결과는 이중 리스트 groupList (인덱스 노드끼리 묶인 그룹 리스트)를 두고 DFS로 순회를 시키면서 GroupList들에 묶고 해당 그룹리스트의 개수를 구해서 반환하는 형태로 풀었다. 아무래도 좀 더 단순하거나 간단한 방식이 있을 듯 하긴 한데 좀 더 다양한 DFS랑 Graph 문제를 풀어봐야 하지 않을까 싶다.

using System.Collections.Generic;

public class Solution
{
    private List<List<int>> graph;

    /// <summary>
    /// 묶음 리스트
    /// </summary>
    private List<List<int>> groupList;

    /// <summary>
    /// 네트워크
    /// https://school.programmers.co.kr/learn/courses/30/lessons/43162
    /// </summary>
    public int solution(int n, int[,] computers)
    {
        // DFS로 푸는 문제
        
        graph = new List<List<int>>(n);

        for (int i = 0; i < n; i++)
        {
            graph.Add(new List<int>());
        }

        for (int i = 0; i < computers.GetLength(0); i++)
        {
            for (int j = 0; j < computers.GetLength(1); j++)
            {
                // i와 j가 같거나 i와 j가 연결되었다는 것은 굳이 j에서 i연결 체크는 할 필요가 없음
                if (i >= j) continue;
                
                // 연결 체크
                if (computers[i, j] == 1)
                {
                    graph[i].Add(j);
                    graph[j].Add(i);
                }
            }
        }
        
        groupList = new List<List<int>>();
        
        for (int i = 0; i < n; i++)
        {
            DFS(i);
        }
        
        return groupList.Count;
    }

    public void DFS(int index)
    {
        int gId = GetGroupIndex(index);
        List<int> targetGroup;

        if (gId < 0)
        {
            var newGroup = new List<int>();
            newGroup.Add(index);
            groupList.Add(newGroup);
            targetGroup = newGroup;
        }
        else
        {
            targetGroup = groupList[gId];
        }
        
        for (int i = 0; i < graph[index].Count; i++)
        {
            int target = graph[index][i];

            if (targetGroup.Contains(target))
            {
                continue;
            }
            
            targetGroup.Add(target);

            DFS(target);
        }
    }

    public int GetGroupIndex(int index)
    {
        int gIndex = -1;
        
        for (int i = 0; i < groupList.Count; i++)
        {
            var gList = groupList[i];
            if (gList.FindIndex(x => x == index) >= 0)
            {
                gIndex = i;
                break;
            }
        }

        return gIndex;
    }
}

✅ 풀이 코드

정말 풀이 코드를 보고 내가 너무 그냥 비효율적으로 풀었구나란 생각이 들었다. 먼저 굳이 GroupList와 같은 걸로 결과를 할 필요가 없다. 저번 문제에서도 자주 나왔던 visited만 잘 활용하면 간결하게 바뀐다는 점. 추가로 이중 리스트 같은 것도 필요가 없다고 한다. 어차피 int[,]로 2차원 배열이 있기 때문에 그걸 그대로 활용하면 된다.. DFS를 호출을 해주고 해당 시작 지점에서 group으로 묶인 것들은 다 방문처리가 되므로 count를 한 번 증가시킨다. 결국 DFS란 하나의 그룹을 다 도는 것이기 때문에 이렇게 간결하게 풀 수 있다는 것을 기억해두자.

public class Solution {
    public int solution(int n, int[,] computers) {
        bool[] visited = new bool[n];
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                DFS(i, visited, computers);
                count++;
            }
        }

        return count;
    }

    private void DFS(int node, bool[] visited, int[,] computers) {
        visited[node] = true;

        for (int i = 0; i < computers.GetLength(1); i++) {
            if (i != node && computers[node, i] == 1 && !visited[i]) {
                DFS(i, visited, computers);
            }
        }
    }
}

🔄 정리

DFS와 Graph 문제라는 것을 보고 어렵게 생각해서 그룹핑을 하고 복잡한 자료구조들이 섞이게 푸는 것보단 핵심이었던 visited를 활용해서 문제를 풀 수 있다는 것을 염두에 두자.