JArchive 프로그래밍 일기

문제

그림 백준 1926

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
​
int n, m; // 세로, 가로
int board[502][502];
int v[502][502]; // 방문했으면 1로 표시
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
​
int cnt, answer; // 그림 개수와 넓이.
​
int bfs(int a, int b){
​
    queue<pair<int,int> > q;
    int num = 0;
​
    // 방문표시 후, 큐에 넣기.
    v[a][b] = 1;
    q.push({a,b});
​
    while(!q.empty()){
​
        int x = q.front().X;
        int y = q.front().Y;
        q.pop();
        num++;
        for(int i = 0; i < 4; i++){
            int tempX = x + dx[i];
            int tempY = y + dy[i];
​
            if(tempX < 0 || tempX >= n || tempY < 0 || tempY >= m) continue; // 범위 초과는 탈출
            if(v[tempX][tempY] == 1) continue; // 이미 방문한거면 지나감
​
            if(board[tempX][tempY] == 1){ // 그림영역이라면 방문표시 후 큐에 넣기.
                board[tempX][tempY] = 2;
                v[tempX][tempY] = 1;
                q.push({tempX, tempY});
            }
        }
    }
​
    return num;
}
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    cin >> n >> m;
​
    for(int a = 0; a < n; a++){
        for(int b = 0; b < m; b++){
            cin >> board[a][b];
        }
    }
​
    for(int a = 0; a < n; a++){
        for(int b = 0; b < m; b++){
​
            if(board[a][b] == 0 || v[a][b] == 1) continue;
            cnt++; //그림 개수 카운트
            answer = max(answer, bfs(a,b)); // 최대 넓이 찾기 
​
        }
    }
​
    cout << cnt << '\n' << answer;
    return 0;
}

리뷰

BFS 기본 형태의 문제다.

인덱스 확인 후 그림영역에 방문 표시를 한다음에 방문한 좌표를 push()를 해줘야하는데.

그거 하나 틀려서 시간을 많이 잡아먹었다.