[C#] 백준 1388번 바닥 장식 (그래프- 깊이 우선 탐색(DFS))

[ 문제 ]

형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.

이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.

기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.

 

[ 코드 ]

1. 내 코드

using System;
using System.Collections.Generic;

class MainClass
{
    static char[][] graph; 

    static void Dfs(int x, int y)
    {
        if (graph[x][y] == '-')
        {
            graph[x][y] = '1'; // 탐색 했으니 1로 변경

            foreach (int _y in new int[] { 1, -1 })
            {
                int Y = y + _y;
                if (Y > 0 && Y < graph[0].Length && graph[x][Y] == '-')
                {
                    Dfs(x, Y);
                }
            }
        }

        if (graph[x][y] == '|')
        {
            graph[x][y] = '1';

            foreach (int _x in new int[] { 1, -1 })
            {
                int X = x + _x;
                if (X > 0 && X < graph.Length && graph[X][y] == '|')
                {
                    Dfs(X, y);
                }
            }
        }
    }

    public static void Main(string[] args)
    {
        string[] nm = Console.ReadLine().Split(); 
        int n = int.Parse(nm[0]);
        int m = int.Parse(nm[1]);

        graph = new char[n][]; 
        for (int i = 0; i < n; i++)
        {
            graph[i] = Console.ReadLine().ToCharArray(); 
        }

        int count = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (graph[i][j] == '-' || graph[i][j] == '|')
                {
                    Dfs(i, j); 
                    count++;
                }
            }
        }

        Console.WriteLine(count); 
    }
}

 

2. 다른 사람 코드

using System;

namespace 백준_알고리즘
{
    internal class Program
    {
        static bool[,] visit;
        static bool[,] map;

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

        static int N, M, Count;

        static void Main()
        {
            int[] Input = Array.ConvertAll(Console.ReadLine().Split(' '), x => int.Parse(x));

            N = Input[0]; 
            M = Input[1];
            visit = new bool[N, M];
            map = new bool[N, M];

            for (int i = 0; i < N; i++)
            {
                string s = Console.ReadLine();
                for (int j = 0; j < M; j++)
                {
                    if (s[j] == '-') { map[i,j] = true; }
                }
            }

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    if (!visit[i,j])
                    {
                        DFS(i,j);
                        Count++;
                    }
                }
            }

            Console.Write(Count);
        }


        private static void DFS(int y, int x)
        {
            visit[y, x] = true;

            //true => '-' => 좌우로만 탐색
            if (map[y,x])
            {
                for (int i = 0; i < 2; i++)
                {
                    int yy = y + dy[i];
                    int xx = x + dx[i];

                    if (yy < 0 || xx < 0 || yy >= N || xx >= M) { continue; }

                    if (!visit[yy,xx] && map[yy,xx]) { DFS(yy, xx); }
                }
            }
            else
            {
                for (int i = 2; i < 4; i++)
                {
                    int yy = y + dy[i];
                    int xx = x + dx[i];

                    if (yy < 0 || xx < 0 || yy >= N || xx >= M) { continue; }

                    if (!visit[yy, xx] && !map[yy,xx]) { DFS(yy, xx); }
                }
            }
        }
    }
}

 

[ 실행화면 ]

case: 1

case: 2

case: 4

---

문제링크: https://www.acmicpc.net/problem/1388

1388번: 바닥 장식