[BOJ/C++] 1926::그림

그림

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	35162	15183	10562	41.888%

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

---

예제 입력 1 복사

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

예제 출력 1 복사

4
9

---

후기

이번 문제는 BFS를 통해 해결해야한다.

이번 문제를 난애하게 만든 것은 알고리즘도 아닌 초기화였다.

 

BFS 탐색을 위해서는 이미 탐색이 끝난 위치를 다시 확인하지 않도록 하기위해 bool 배열을 같이 사용한다.

이때, 발생한 문제가 초기화를 선언하여도 모든 bool 변수가 초기화가 되지 않았다.

 

// 아래 초기화를 다 해봤다.
bool visited[rows][column];
bool visited[rows][column] = {{0}};
bool visited[rows][column] = {{false, }, };

3 3
1 0 1
0 0 0
1 0 1
Before : 0, 0 bool : 0
Before : 0, 1 bool : 80		// 뭔가 나온다...
Before : 0, 2 bool : 148	// 뭔가 나온다...
Before : 1, 0 bool : 0
Before : 1, 1 bool : 0
Before : 1, 2 bool : 0
Before : 2, 0 bool : 0
Before : 2, 1 bool : 0
Before : 2, 2 bool : 0

 

컴파일 버전에 따른 오류인지 모르겠다...

아마 이전 메모리 값에 남아있던 쓰레기 값은 것 같기도 한데 memset으로 초기화 해버려야할지도...

 

그래서 해봤다. memset 초기화 및 일반 배열 초기화, vector를 활용한 초기화까지

그리고 백준에 제출했더니 다음과 같았다.

 

 

위 2개가 memset을 사용한 것이고 가장 아래가 vector로 초기화한 것이다.

memset이 vector 생성자를 사용하는 것보다 오래걸렸다. 뭐 생성하자마자 초기화 되는 것과 한번 할당하고 초기화 하는 것의 차이일지도 모른다.

심지어 배열을 바로 0으로 초기화 하는 방법은 결과가 틀렸다고 나왔다.

 

이제 간단하게 어떻게 동작하는지만 알아보고 끝내자.

 

1. 정보를 입력 받는다.
2. 총 배열의 크기만큼 visited 배열을 생성한다.
3. 1이 있는 위치가 나올때까지 순환한다.
4. 1을 찾으면 visited 배열을 통해 이미 방문한 노드인지 확인한다.
5. 한 번도 방문하지 않은 노드라면 큐에 저장하고 주변 노드가 1인지 확인한다.
   • 총 그림의 개수를 증가시킨다.
6. 모든 방향(4방향)을 확인하여, 값이 1이면서 방문하지 않은 위치를 큐에 저장한다.
7. 큐가 비어있을 때까지 반복하여 연결된 모든 1의 노드를 방문한다.
   • 방문할 때마다 연결 노드의 크기를 저장한다.
8. 큐가 더이상 존재하지 않는다면 최종적으로 방문한 노드 개수를 확인하여 가장 큰 그림인지 확인한다.

 

#include <iostream>
#include <utility>
#include <vector>
#include <queue>
using namespace std;

void BFS(vector<vector<int>> map, int rows, int column, int *biggest, int *paintings);

int main(void) {
    ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

    int paintings = 0;
    int biggestPaint = 0;

    int rows, column;
    cin >> rows >> column;
    
    vector<vector<int>> museum(rows, vector<int>(column, 0));

    for (int k = 0; k < rows; k++) {
        for (int j = 0; j < column; j++) {
            cin >> museum[k][j];
        }
    }

    BFS(museum, rows, column, &biggestPaint, &paintings);

    cout << paintings << '\n';
    cout << biggestPaint << '\n';

    return 0;
}


// BFS 탐색
void BFS(vector<vector<int>> map, int rows, int column, int *biggest, int *paintings)
{
    int currentSize = 0;
    vector<vector<bool>> visited(rows, vector<bool>(column, 0));
    queue<pair<int,int>> path;

    for (int row = 0; row < rows; row++) {
        for (int col = 0; col < column; col++) {
            // If on a visited node
            // Continue Search
            if (visited[row][col]) {
                continue;
            }

            // If the node is new, check for path
            visited[row][col] = true;

            // Abandoned the node, If it's untraceable
            if (map[row][col] == 0) {
                continue;
            }
            
            // Add current node
            path.push({row, col});
            currentSize = 1;
            (*paintings)++;

            while (!path.empty()) {
                pair<int, int> node = path.front();
                path.pop();

                // Check directions
                // check up
                int direction = node.first - 1;
                if (direction > -1 && !visited[direction][node.second] && map[direction][node.second] != 0) { 
                    visited[direction][node.second] = true;
                    path.push({direction, node.second});
                    currentSize++;
                }
                
                // check down
                direction = node.first + 1;
                if (direction < rows && !visited[direction][node.second] && map[direction][node.second] != 0) { 
                    visited[direction][node.second] = true;
                    path.push({direction, node.second});
                    currentSize++;
                }
                
                // check right
                direction = node.second + 1;
                if (direction < column && !visited[node.first][direction] && map[node.first][direction] != 0) { 
                    visited[node.first][direction] = true;
                    path.push({node.first, direction});
                    currentSize++;
                }
                
                // check left
                direction = node.second - 1;
                if (direction > -1 && !visited[node.first][direction] && map[node.first][direction] != 0) { 
                    visited[node.first][direction] = true;
                    path.push({node.first, direction});
                    currentSize++;
                }
            }

            // Find biggest painting
            if (currentSize > *biggest) {
                *biggest = currentSize;
            }
        }
    }
}