[BOJ] 1012 : 유기농 배추

1012 : 유기농 배추

풀이

BFS

몇번 풀어본 유형이다. 그루핑 해주는 문제 종류라고 볼 수 있겠다.

check가 굳이 필요없어서 안썼는데,

큐에 push하고 arr를 0으로 만드는게 아니라

큐에 pop하기 전에 arr를 0으로 만들었더니

중복된 큐가 많이 들어가서 메모리 초과가 떴다.

push하고 arr를 0으로만드니까 잘 풀렸다.(주의해야겠다)

첫번째 풀이는 전체맵을 탐색(이중반복)하면서

1값이 남아있으면 ans++하고, 퍼질수 있는 범위만큼 bfs로 탐색해 0으로 만들어 버리는 코드이다.

두번째 풀이는 함수로 따로 빼지 않고, 큐 두개로 하는 풀이이다.

큐에 미리 1값위치를 넣어둔 후, 첫번째 큐에서 1값이 남아있으면

두번째 큐로가서 퍼질 수 있는 범위만큼 bfs로 탐색해 0으로 만들어 버리는 코드이다.

두번째 풀이가 메모리가 130KB만큼 더나왔다. 효율성은 데이터에따라 다를것같다.

코드

첫번째

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int arr[50][50];
const int dx[] = { 0,-1,0,1 };
const int dy[] = { 1,0,-1,0 };
int m, n, k;

void f(int a, int b) {
    queue<pair<int, int>> q;
    q.push({ a,b });
    arr[a][b] = 0;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (nx >= 0 && nx < n&&ny >= 0 && ny < m&&arr[nx][ny] == 1) {
                q.push({ nx,ny });
                arr[nx][ny] = 0;
            }
        }
    }
}

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

    int T;
    cin >> T;
    while (T--) {
        memset(arr, 0, sizeof(arr));
        
        cin >> m >> n >> k;
        int ans = 0;
        for (int i = 0; i < k; i++) {
            int a, b;
            cin >> a >> b;
            arr[b][a] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 1) {
                    ans++;
                    f(i, j);
                }
            }
        }

        cout << ans << '\n';
    }
    return 0;
}

코드

두번째 코드

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int arr[50][50];
const int dx[] = { 0,-1,0,1 };
const int dy[] = { 1,0,-1,0 };
queue<pair<int, int>> q;
queue<pair<int, int>> q2;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        memset(arr, 0, sizeof(arr));
        int m, n, k;
        cin >> m >> n >> k;

        for (int i = 0; i < k; i++) {
            int a, b;
            cin >> a >> b;
            arr[b][a] = 1;
            q.push({ b,a });
        }
        int ans = 0;
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if (arr[x][y] == 0) {
                continue;
            }
            ans++;
            arr[x][y] = 0;
            for (int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && arr[nx][ny] == 1) {
                    q2.push({ nx,ny });
                    arr[nx][ny] = 0;
                }
            }
            while (!q2.empty()) {
                int xx = q2.front().first;
                int yy = q2.front().second;
                q2.pop();
                
                for (int dir = 0; dir < 4; dir++) {
                    int nxx = xx + dx[dir];
                    int nyy = yy + dy[dir];
                    if (nxx >= 0 && nxx < n && nyy >= 0 && nyy < m && arr[nxx][nyy] == 1) {
                        q2.push({ nxx,nyy });
                        arr[nxx][nyy] = 0;
                    }
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

Written on March 15, 2019