[백준] 1926번 그림

문제: 1926번: 그림

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;


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

    int n, m; // n: 세로크기, m: 가로크기
    cin >> n >> m;
    vector<vector<int>> board(n);
    vector<vector<bool>> visit(n);

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

    for (int i = 0; i < n; i++) {
        board[i] = vector<int>(m);
        visit[i] = vector<bool>(n);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }

    int count = 0; // 그림 개수
    int maxWidth = 0;
    // 이중 for 문 돌면서 시작점을 지정해서 BFS 돌리기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 이미 방문 표시가 되어 있거나 방문 할 수 없는 곳이면 건너뛰도록..
            if (visit[i][j] == true || board[i][j] == 0) continue; 

            count++; // 그림 개수 +1 해주기..

            int tmpCnt = 0; // 이 값이 maxWidth 보다 크면 maxWidth 값이 tmpCnt 가 됨.
            queue<pair<int, int>> nexts;
            pair<int, int> start = make_pair(i, j); // i: 행, j: 열
            nexts.push(start);
            visit[i][j] = true; // 방문 표시

            // 비어있지 않을 때까지 돌리기
            while (!nexts.empty()) {
                pair<int, int> cur = nexts.front(); // 맨 앞 요소 가져오기
                nexts.pop(); // 없애깅
                tmpCnt++;

                for (int k = 0; k < 4; k++) {
                    int nx = cur.first + dx[k];
                    int ny = cur.second + dy[k];

                    // 범위 벗어나면 건너뛰도록..
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    // 이미 방문했거나 갈 수 없는 곳이면 건너뛰도록..
                    if (visit[nx][ny] == true || board[nx][ny] == 0) continue;

                    // 방문할 수 있는 곳이면 추가하고 방문 표시
                    nexts.push(make_pair(nx, ny));
                    visit[nx][ny] = true; // 방문 표시
                }
            }

            if (maxWidth < tmpCnt)
                maxWidth = tmpCnt; // 값 갱신
        }
    }
    cout << count << "\n" << maxWidth;


    return 0;
}

 

음 BFS 를 살짝 응용한 문제라고 할 수 있을 것 같다.

 

그림의 개수는 BFS 를 시작할 수 있는 곳의 개수와 같다. 이중 포문을 돌면서 이미 방문 표시 된 곳이나 방문 할 수 없는 곳을 제외하고는 방문할 수 있는 곳이다. 즉, if 문에서 걸러지지 않은 경우에는 count 값을 1 증가시켜주면 된다.

 

그 다음으로는 그냥 전형적인 BFS 문제이다. 현재 위치에서 상하좌우를 확인하고 방문할 수 있는 곳이면 방문 표시를 한 다음에 큐에 넣어주는 걸 반복하면 된다. 그림의 너비는 큐에서 값을 뺀 횟수와 같다.

 

모든 그림 중 가장 넓은 너비를 구하기 위해서는 BFS 를 시작할 때 tmpCnt 의 값을 0으로 설정해주고 BFS 를 돌면서 이 값을 갱신하고, 마지막에 maxWidth 와 비교해서 tmpCnt 의 값이 더 크다면 maxWidth 의 값을 tmpCnt 의 값으로 갱신해주는 방법이 있다.

 

 

 

참고자료:

BaaaaaaaarkingDog | [실전 알고리즘] 0x09강 - BFS

[실전 알고리즘] 0x09강 - BFS