C# 네트워크 - DFS BFS / 프로그래머스 [Lv.3]

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

 

 

나의 풀이

public int solution(int n, int[,] computers) 
{
    int answer = 0;

    var open = new Stack<int>();
    var close = new HashSet<int>();

    for(int i = 0; i < n; ++i)
    {
        if(close.Contains(i)) continue;

        ++answer;
        open.Push(i);
        while(open.Count > 0)
        {
            int popIndex = open.Pop();
            for(int k = 0; k < n; ++k)
            {
                if(close.Contains(k)) continue;
                if(computers[popIndex, k] == 1)
                {
                    close.Add(k);
                    open.Push(k);
                }
            }
        }
    }

    return answer;
}

open close 마킹 방식으로 반복문 풀이.

 

다른 사람 풀이

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

    int answer = 0;

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

public static void DFS(int[,] computers, bool[] visited, int start)
{
    visited[start] = true;
    for(int i = 0; i < computers.GetLength(0); i++)
    {
        if (computers[start, i] == 1 && !visited[i])
            DFS(computers, visited, i);
    }
}

visited를 마킹하는 방식으로 재귀식 DFS 를 이용한 풀이.