[백준] 1926 - 그림

1. 문제

1926번: 그림

2. 개요

어떤 도화지에 그림들이 그려져 있다.

도화지에 그려진 그림의 갯수와 이 그림 중 가장 큰 그림의 넓이를 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

0, 0부터 탐색하며 1을 찾는다면 그림이 있다는 것이므로 그림의 갯수를 1늘려주고 DFS를 실행한다.

연결된 1마다 영역의 넓이를 1씩 늘려준다. DFS를 마쳤다면 최대 넓이를 기존값과 비교해 갱신한다.

n, m까지 탐색을 모두 마쳤다면 그림의 수와 최대 넓이를 출력한다.

3-2. Python

import sys

sys.setrecursionlimit(100000)

n, m = map(int, sys.stdin.readline().split())

board = []
visited = [[False for i in range(m)] for j in range(n)]

num, maxarea = 0, 0

for i in range(n):
    board.append(list(map(int, sys.stdin.readline().split())))

def DFS(y, x, cnt):
    dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]

    for i in range(4):
        nextY, nextX = y + dirY[i], x + dirX[i]

        if nextY < 0 or nextY >= n or nextX < 0 or nextX >= m:
            continue

        if visited[nextY][nextX] == True:
            continue

        if board[nextY][nextX] == 0:
            continue

        visited[nextY][nextX] = True
        cnt = DFS(nextY, nextX, cnt + 1)

    return cnt

for i in range(n):
    for j in range(m):
        if visited[i][j] == True:
            continue

        if board[i][j] == 0:
            continue

        visited[i][j] = True
        num += 1
        maxarea = max(DFS(i, j, 1), maxarea)

print(num)
print(maxarea)

3-3. C#

namespace boj_1926
{
    internal class Program
    {
        static int n;
        static int m;
        static int[,] board;
        static bool[,] visited;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();
            n = int.Parse(input[0]);
            m = int.Parse(input[1]);

            board = new int[n, m];
            visited = new bool[n, m];

            int num = 0;
            int maxarea = 0;

            for (int i = 0; i < n; i++)
            {
                int[] row = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
                for (int j = 0; j < m; j++)
                {
                    board[i, j] = row[j];
                }
            }

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (board[i, j] == 0)
                        continue;

                    if (visited[i, j] == true)
                        continue;

                    num++;
                    visited[i, j] = true;
                    maxarea = (int)MathF.Max(DFS(i, j, 1), maxarea);
                }
            }

            sw.WriteLine(num);
            sw.WriteLine(maxarea);
            sw.Close();
        }

        static int DFS(int y, int x, int cnt)
        {
            int[] dirY = { -1, 0, 1, 0 };
            int[] dirX = { 0, -1, 0, 1 };

            for (int i = 0; i < 4; i++)
            {
                int nextY = y + dirY[i];
                int nextX = x + dirX[i];

                if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= m)
                    continue;

                if (board[nextY, nextX] == 0)
                    continue;

                if (visited[nextY, nextX] == true)
                    continue;

                visited[nextY, nextX] = true;
                cnt = DFS(nextY, nextX, cnt + 1);
            }

            return cnt;
        }
    }
}