1012. 유기농 배추

백준 1012번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

1012번: 유기농 배추

풀이

아이디어

옛날에 첫 BFS문제를 이 문제로 풀었었던 것 같은데 .. (아련) 아무튼 이 문제는 BFS로 풀어줬다.

예전에는 어떤 문제를 BFS로 풀어야 할 지 몰라서 많이 헤맸었던 기억이 있는데 이 문제처럼 뭔가 넓은 구역을 돌아다니면서 인접한 구역을 찾아다니는 문제는 BFS로 푸는게 이해하기도 쉽고 깔끔한 것 같다.

bfs 함수 안에서 BFS를 진행해 줬는데… 간단히 bfs의 과정을 설명하면 아래와 같다.

• 시작 지점을 큐에 넣는다.
• 큐가 빌 때까지 아래의 과정을 반복한다.
  • 큐.pop()
  • 상하좌우 인접한 지점 중에 방문하지 않은 지점을 큐에 push (map의 범위 벗어나는지 확인!, 배추가 있는 지점인지 확인!)
  • 큐에 push한 지점을 방문했다고 표시한다.

이렇게 모든 맵을 돌아다니면서 인접한 배추 모음의 개수를 세어 주면 그 개수가 바로 필요한 배추흰지렁이의 최소 개수가 된다.

아 간혹 내가 실수하는 부분이라서 적어두는건데… 테스트 케이스가 주어지기 때문에 매 테스트케이스마다 밭의 정보, 방문기록을 초기화 해 두는것을 잊지 말자…ㅎ

코드

/*
2022-2-9
1012_유기농 배추
https://www.acmicpc.net/problem/1012
*/

#include <iostream>
#include <queue>
#include <cstring>  // memset
#include <utility>  // pair
using namespace std;


int map[51][51];
bool visited[51][51];
int m, n; // 밭의 가로길이, 세로길이
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
queue<pair<int, int> > q;   // bfs

void bfs();

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

    int t;  // test case
    int k;  // 배추의 개수
    int kx, ky;  // 배추의 위치
    int cnt;    // 배추흰지렁이의 수

    cin >> t;
    while (t--){
        cin >> m >> n >> k;
        for(int i = 0; i < n; i++){
            memset(map[i], 0, sizeof(map[i]));
            memset(visited[i], false, sizeof(visited[i]));
        }
        while (k--){
            cin >> kx >> ky;
            map[ky][kx] = 1;
        }
        cnt = 0;
        for (int y = 0; y < n; y++){
            for(int x = 0; x < m; x++){
                if (map[y][x] == 1 && visited[y][x] == false){
                    cnt++;
                    q.push(make_pair(x, y));
                    bfs();
                }
            }
        }
        cout << cnt << '\n';
    }

    return (0);
}

void bfs(){
    int x, y;
    while (!q.empty()){
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            if ((y + dy[i] < 0) || (y + dy[i] >= n) || (x + dx[i] < 0) || (x + dx[i] >= m))
                continue;
            else if (map[y + dy[i]][x + dx[i]] != 1 || visited[y + dy[i]][x + dx[i]] == true)
                continue;
            else {
                q.push(make_pair(x + dx[i], y + dy[i]));
                visited[y + dy[i]][x + dx[i]] = true;
            }
        }
    }
}