백준 1012 (유기농 배추) c++

문제

1012번: 유기농 배추

Flood Fill Algorithm : 어떤 칸과 연결된 영역을 찾는 알고리즘

가로 M과 세로 N이 주어지고 배추의 위치 (M(가로), N(세로)) 이 주어 집니다.

다음과 같이 1끼리 인접한 부분(상하좌우)이 몇개인지 출력하는 문제입니다.

위의 그림에서는 5개입니다.

 

주어지는 위치가 처음에 가로, 세로가 주어지므로 행렬로 생각할 때 주의해야합니다.

M은 행이 아닙니다. 열입니다. 

N은 열이 아닙니다. 행입니다.

즉 행열이 반대로 주어지는 겁니다.

저는 처음에 이것을 착각해서 계속 틀렸습니다.

 

dfs와 bfs 두 가지로 구현하여 해결하였습니다.

먼저 dfs입니다.

저는 처음에 bool 함수를 이용해 탐색을 한 위치는 true로 바꿔주었는데 이번 캠프에서 멘토님의 코드는

굳이 필요없었습니다.

14번째 줄을 보면 탐색을 한 부분은 그냥 0으로 바꿔주면 됩니다.

16, 17 번째 줄을 보면 상하좌우로 탐색하기 위한 준비 단계입니다.

18번째 줄을 보면 저는 이 코드를 빠뜨려서 틀렸습니다.

예를 들어 arr[0][0]에서 탐색을 하다가 상하좌우로 움직일때 arr[-1][0] 으로는 갈 수 없습니다.

또한 M, N이 각각 50이면 arr[49][49]에서 arr[50][49] 로는 갈 수 없습니다.

이를 반영한게 18번째 코드입니다.

 

그 다음 bfs 코드입니다.

6, 7번째 코드는 8번째 코드로 대체가능합니다.

---

전체 코드입니다.

dfs

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
using namespace std;
using ll = long long;
void dfs(int x,int y);
int arr[51][51];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int m, n, k, ans;
int main() {
    ios_base::sync_with_stdio(), cin.tie(), cout.tie();
    int t;
    cin >> t;
    while (t--) {
        memset(arr, 0, sizeof(arr));
        ans = 0;
        cin >> m >> n >> k;
        for (int i = 0; i < k; i++) {
            int x, y;
            cin >> y>> x;
            arr[x][y] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j]==1) {
                    ans++;
                    dfs(i, j);
                }
 
            }
        }
        cout << ans << '\n';
    }
 
 
    return 0;
}
void dfs(int x,int y) {
    arr[x][y] = 0; //탐색했다고 표시해줌
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
            if (arr[nx][ny] == 1)
                dfs(nx, ny);
        }
    }
}
 

bfs

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
using namespace std;
using ll = long long;
int arr[51][51];
int m, n, k;
queue<pair<int, int>>q;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
void bfs(int x, int y);
int main() {
    ios_base::sync_with_stdio(), cin.tie(), cout.tie();
    int t;
    cin >> t;
    while (t--) {
        int ans = 0;
        memset(arr, 0, sizeof(arr));
        cin >> m >> n >> k;
        for (int i = 0; i < k; i++) {
            int x, y;
            cin >> x >> y;
            arr[y][x] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 1) {
                    ans++;
                    bfs(i, j);
                }
            }
        }
        cout << ans << '\n';
    }
 
 
    return 0;
}
void bfs(int x, int y) {
    q.push({ x,y });
    arr[x][y] = 0;
    while (!q.empty()) {
        int X = q.front().first;
        int Y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = X + dx[i];
            int ny = Y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (arr[nx][ny] == 1) {
                    arr[nx][ny] = 0;
                    q.push({ nx,ny });
                }
            }
        }
    }
    
}