[필수 알고리즘] DFS

DFS란?

- 바로가기

[필수 알고리즘] 그래프 탐색

- Stack과 재귀함수를 이용해 풀수 있음

- 그래프 탐색은 BFS로 대부분 풀수 있으며, DFS는 재귀 함수를 사용하기 위함이며 백트래킹에서 효율적이라함

 

재귀함수란?

- 자기 자신을 다시 호출하는 함수

- DFS, 백트래킹에서 주로 사용

 

풀이방법

- 시작 Vertex 찾기

- 연결된 Vertex를 계속 찾음(끝날때 까지)

- 더이상 연결된 Vertex 없을 경우 다음 진행

- 1 -> 2 -> 3 -> 4 -> 6 -> 5

 

시간 복잡도

- O(V+E)

 

자료구조

- 검색할 그래프 : 2차원배열

- 방문여부 확인 : 2차원 배열(재방문 금지)

 

문제풀이

- 백준 2667

 

1. 

public class num_2667
{
    static int[] dy = { 0, 1, 0, -1 };
    static int[] dx = { 1, 0, -1, 0 };
    public static void Main()
    {
        int n = Convert.ToInt32(Console.ReadLine());
        int[][] arr = new int[n][];
        bool[][] chk = new bool[n][];

        List<int> result = new List<int>();

        for (int i = 0; i < n; i++)
        {
            string line = Console.ReadLine();
            arr[i] = new int[n];
            for (int j = 0; j < n; j++)
            {
                // 문자열을 한 글자씩 숫자로 변환
                arr[i][j] = line[j] - '0';
            }
            chk[i] = new bool[n];
        }
    }
}

- 이전 BFS와 동일하게 dy, dx를 미리 정의 해주고 arr, chk를 각각 정의해준 후 값을 받아온다.

- "int n = Convert.ToInt32(Console.ReadLine());"로 값을 받아오니 앞글자 0이 공백으로 표기되어 받는 방식을 문자열 한글자씩 받아오도록 변경

 

2. 

static int Each = 0;

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        if (arr[i][j] == 1 && !chk[i][j])
        {
            //방문 체크 표시
            chk[i][j] = true;
            //DFS로 크기 구하기
            Each = 0;
            Dfs(i, j, n, arr, chk);
            //값 저장 
            result.Add(Each);
        }
    }
}

static void Dfs(int i, int j, int n, int[][] arr, bool[][] chk)
{
    Each++;
    for (int x = 0; x < 4; x++)
    {
        int ny = i + dy[x];
        int nx = j + dx[x];

        if (0 <= ny && ny < n && 0 <= nx && nx < n)
        {
            if (arr[ny][nx] == 1 && !chk[ny][nx])
            {
                chk[ny][nx] = true;
                Dfs(ny, nx, n, arr, chk);
            }
        }
    }
}

- 2중 for문을 이용해 1인지 false인지 체크

- "static int Each = 0;" 전역변수로 선언해 준 후 Dfs가 실행될때마다 +1 증가

 

3.

result.Sort();
Console.WriteLine(result.Count);
for (int i = 0; i < result.Count; i++)
{
    Console.WriteLine(result[i]);
}

- 문제에 맞게 정렬 후 결과 출력

 

최종코드

/*
1. 아이디어
- 2중 for, 값이 1&& 방문X => DFS
- DFS를 통해 찾은 값을 저장 후 출력
2. 시간 복잡도
- DFS : O(V+E)
- V, E : N^2, 4N^2
- V + E : 5N^2 ~= N^2 ~ = 625 >> 가능
3. 자료구조
- 그래프 저장 : int[][]
- 방문여부 : bool[][]
- 결과값 : int[]
*/

public class num_2667
{
    static int[] dy = { 0, 1, 0, -1 };
    static int[] dx = { 1, 0, -1, 0 };
    static int Each = 0;
    public static void Main()
    {
        int n = Convert.ToInt32(Console.ReadLine());
        int[][] arr = new int[n][];
        bool[][] chk = new bool[n][];

        List<int> result = new List<int>();

        for (int i = 0; i < n; i++)
        {
            string line = Console.ReadLine();
            arr[i] = new int[n];
            for (int j = 0; j < n; j++)
            {
                // 문자열을 한 글자씩 숫자로 변환
                arr[i][j] = line[j] - '0';
            }
            chk[i] = new bool[n];
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (arr[i][j] == 1 && !chk[i][j])
                {
                    //방문 체크 표시
                    chk[i][j] = true;
                    //DFS로 크기 구하기
                    Each = 0;
                    Dfs(i, j, n, arr, chk);
                    //값 저장 
                    result.Add(Each);
                }
            }
        }

        result.Sort();
        Console.WriteLine(result.Count);
        for (int i = 0; i < result.Count; i++)
        {
            Console.WriteLine(result[i]);
        }
    }

    static void Dfs(int i, int j, int n, int[][] arr, bool[][] chk)
    {
        Each++;
        for (int x = 0; x < 4; x++)
        {
            int ny = i + dy[x];
            int nx = j + dx[x];

            if (0 <= ny && ny < n && 0 <= nx && nx < n)
            {
                if (arr[ny][nx] == 1 && !chk[ny][nx])
                {
                    chk[ny][nx] = true;
                    Dfs(ny, nx, n, arr, chk);
                }
            }
        }
    }
}

 

참고영상

- 바로가기