[백준] 1926 그림

문제 설명

https://www.acmicpc.net/problem/1926

1926번: 그림

어떤 도화지에 그림이 그려져 있을때, 그 그림의 개수와 그 그림 중 넓이가 가장 넓은 것의 넓이 구하기

 

문제 풀이법

그래프를 모두 방문하는 문제이기 때문에 DFS, BFS중 어느 것을 사용하여도 관계가 없다

따라서 2가지 방법으로 풀어보았다

 

도화지의 값을 저장하는 arr배열, 도화지의 값을 방문했는지 저장하는 visited배열은 공통적으로 필요하다

• BFS
  • 큐에 arr의 값이 1이며, visited가 0인 좌표를 저장하며, 상하좌우를 이동하며 비교한다
  • 상하좌우의 값이 범위를 벗어나거나, visited가 1이 아니거나, arr의 값이 0이면 넘어가고, 그렇지 않은 수는 큐에 저장한다
  • 재귀를 돌지 않기에 그림의 크기를 구하기 위해 지역변수를 사용하여 그림의 크기 값을 저장
  • 큐에 더이상 값이 존재하지 않을 때까지 while문을 돌면서 반복한다
• DFS
  • 상하좌우를 이동하면서 상하좌우의 값이 범위를 벗어나거나, arr의 값이 0이면 넘어가고 다시 DFS함수를 호출하며 재귀를 돈다
  • 만일 visited가 1이면 그대로 빠져나간다
  • 재귀를 돌기에 그림의 크기는 전역변수를 사용하며 저장한다

 

소스 코드

BFS 풀이

#include <iostream>
#include <utility>
#include <queue>

using namespace std;

int arr[501][501] = { 0 };
int visited[501][501] = { 0 };

int n, m;

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

int bfs(int y, int x)
{
    if (visited[y][x] == 1)
        return 0;
        
    visited[y][x] = 1;
    queue<pair<int, int>> q;
    q.push({y, x});
    
    int sum;
    
    sum = 1;
    while (!q.empty())
    {
        y = q.front().first;
        x = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (nx < 0 || ny < 0 || ny >= n || nx >= m)
                continue;
            if (arr[ny][nx] == 1 && visited[ny][nx] == 0)
            {
                visited[ny][nx] = 1;
                q.push({ny, nx});
                sum++;
                
            }
        }
    }
    
    return (sum);
}

int main()
{
   
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
        }
    }
    
    int max_size = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (arr[i][j] == 1 && visited[i][j] == 0)
            {
                int tmp;
                tmp = bfs(i, j);
                cnt++;
                if (tmp > max_size)
                    max_size = tmp;
            }
        }
    }
    
    printf("%d\n", cnt);
    printf("%d\n", max_size);
    
    return 0;
}

 

DFS 풀이

#include <iostream>

using namespace std;

int arr[501][501] = { 0 };
int visited[501][501] = { 0 };

int n, m;
int tmp;

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

void dfs(int y, int x)
{
    if (visited[y][x] == 1)
        return ;

    visited[y][x] = 1;
    tmp++;
    
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (nx < 0 || ny < 0 || ny >= n || nx >= m || arr[ny][nx] == 0)
            continue;
        dfs(ny, nx);
    }
}

int main()
{
   
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
        }
    }
    
    int max_size = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (arr[i][j] == 1 && visited[i][j] == 0)
            {
                tmp = 0;
                dfs(i, j);
                cnt++;
                if (tmp > max_size)
                    max_size = tmp;
            }
        }
    }
    
    printf("%d\n", cnt);
    printf("%d\n", max_size);
    
    return 0;
}