A082:ショッピングモール建設計画 - DFS 기본

문제요약

호수가 끊기지 않도록 쇼핑몰을 건설할 수 있는 경우의 수

---

난이도

Rank A

---

풀이 포인트

• DFS 기본: 연결 요소 개수 구하기

---

REVIEW

 

DFS 공식 엄청나게 오랜만에 구현하려니 기억이 안나더라.

 

1) 전체 그리드에서 탐색을 시작할 곳 설정.

2) 거기서 부터 이어진 대로 탐색시작. 탐색 완료 시 cnt++;

3) 1,2,를 전체 칸의 수 만큼 반복해서 진행하면 연결 요소의 개수가 구해짐

 

즉, 탐색 시작할 칸의 좌표(x,y)를 DFS 함수에 넣어 탐색 시작하고, 방문 배열 값 관리해주면서 중복되지 않게 탐색하면 됌!

 

원리 한 번 다시 복기해둠

 

---

CODE

using System;

class Program
{
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
    static bool[,] visited;
    static int h, w;

    static void Main()
    {
        var line = Console.ReadLine().Split();
        h = int.Parse(line[0]);
        w = int.Parse(line[1]);
        int total = h * w;

        char[,] grid = new char[h, w];

        for (int i = 0; i < h; i++)
        {
            var line2 = Console.ReadLine();
            for (int j = 0; j < w; j++)
            {
                grid[i, j] = line2[j];
            }
        }

        int cnt = 0;

        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (grid[i, j] == '.') continue;

                char[,] copied = (char[,])grid.Clone();
                copied[i, j] = '.';

                if (IsSeparated(copied)) cnt++;
            }
        }

        Console.WriteLine(total - cnt);
    }

    static bool IsSeparated(char[,] input)
    {
        visited = new bool[h, w];
        int count = 0;

        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (!visited[i, j] && input[i, j] == '#')
                {
                    Dfs(i, j, input);
                    count++;
                    if (count >= 2) return true;  
                }
            }
        }

        return false; 
    }

    static void Dfs(int x, int y, char[,] input)
    {
        visited[x, y] = true;

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

            if (nx >= 0 && nx < h && ny >= 0 && ny < w)
            {
                if (!visited[nx, ny] && input[nx, ny] == '#')
                {
                    Dfs(nx, ny, input);
                }
            }
        }
    }
}