BOJ/백준 - 1012 유기농 배추 C++

문제 풀 때 x랑 y를 잘못 넣어서 고생을 좀 했다.

 

두번 다시 헷갈리지 않게 적어놓는다...ㅠㅠ

 

1.

arr[x][y]

 

2.

arr[y][x]

 

 

잘 보고 풀자~!

 

나는 arr[y][x]가 더 익숙해서 그렇게 풀었다.

 

 

* 그리고 초기화를 할 때, for문을 이용해서 하지 않았다.

#include <string.h>
#include <cstring>

void* memset(void* ptr, int value, size_t num);

memset을 이용해서 더 간단하게 초기화하자.

 

 

 

1. dfs 풀이

 

 

2. bfs 풀이

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#define MAX 51
using namespace std;
 
int T, M, N, K;
int visit[MAX][MAX];
int farm[MAX][MAX];
int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0,1,-1 };
 
queue<pair<int, int>> q;
 
 
void bfs(int y, int x) {
    
    q.push({ y,x });
    
    while(!q.empty()) {
        int curx = q.front().second;
        int cury = q.front().first;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = curx + dx[i];
            int ny = cury + dy[i];
 
            if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
            if (!visit[ny][nx] && farm[ny][nx]) {
                visit[ny][nx] = 1;
                q.push({ ny,nx });
            }
            
        }
 
    }
}
 
int main() {
 
    cin >> T;
 
    while (T--) {
        int cnt = 0;
        cin >> M >> N >> K;
 
        for (int i = 0; i < K; i++) {
            int x, y;
            cin >> x >> y;
 
            farm[y][x] = 1;
        }
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visit[i][j] == 0 && farm[i][j] == 1) {
                    cnt++;
                    bfs(i, j);
                }
            }
        }
 
        cout << cnt << '\n';
 
        //초기화, #include <stdio.h>
        memset(farm, 0, sizeof(farm));
        memset(visit, 0, sizeof(visit));
    }
 
 
    return 0;
}