백준 1012번 유기농 배추

문제 링크 : https://www.acmicpc.net/problem/1012

배추가 있는 영역의 갯수를 세는 문제이다.

1. 배추가 있는 곳의 좌표를 입력받아 int형 2차원배열 map에 표시해주었다

2. map의 좌표를 순서대로 탐색하며 값이 1이고 방문하지 않은 좌표를 발견하면 bfs로 탐색을 하였고 bfs를 실행하는 횟수를 세서 출력하였다.

c++로 풀어서 제출하니 실행시간이 0ms로 나와서 놀랐다. 자바보다 빠르다는 건 알고있었지만 이정로도 차이가 많이 날줄은 몰랐다.

c++ 연습을 하려고 c++로 짰는데 문법이 익숙하지않아서 버벅댔다. 그래서 코드가 이쁘지 않을수도 있다.

풀고나서 다른사람들의 소스코드를 보니 visit배열을 사용하지않고 그냥 map배열의 1값을 0으로 지우는 방법으로 짠 사람도 있었고,

map의 좌표를 다 탐색하지않고 배추정보 입력시 좌표값을 vector에 넣어 뒀다가  그 좌표만을 탐색하는 방법으로 짠 사람도 있었다.

두 방법다 효율을 높일수있는 방법이지만 난 아직 c++문법이 익숙치 않아서 그냥 기본적인 방법으로 푼것으로 만족하였다.

다음에 비슷한 경우를 만나면 저런 방법을 사용해봐야겠다.

아래는 소스코드이다.

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
 
int m, n;
int map[50][50];
bool visit[50][50];
int dy[4] = { 0, 0, -1, 1 };
int dx[4] = { -1, 1, 0, 0 };
 
void bfs(int y, int x) {
    visit[y][x] = true;
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
 
    while (!q.empty()) {
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
            if (map[ny][nx] == 1 && visit[ny][nx] == false) {
                visit[ny][nx] = true;
                q.push(make_pair(ny, nx));
            }
        }
    }
}
 
int main()
{
    int t, k, count;
    cin >> t;
 
    for (int i = 0; i < t; i++) {
        cin >> m >> n >> k;
        count = 0;
        for (int j = 0; j < n; j++) {
            memset(map[j], 0, sizeof(int) * 50);
            memset(visit[j], false, sizeof(int) * 50);
        }
 
        for (int j = 0; j < k; j++) {
            int x, y;
            cin >> x >> y;
            map[y][x] = 1;
        }
 
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < m; b++) {
                if (map[a][b] == 1 && visit[a][b] == false) {
                    bfs(a, b);
                    count++;
                }
            }
        }
 
        cout << count << endl;
    }
}