BOJ 1012 유기농 배추

유기농 배추 [실버2]

---

문제 링크

https://www.acmicpc.net/problem/1012

풀이

테스트 케이스 별 배추의 위치마다 dfs를 수행한 뒤, dfs 시작 횟수를 반환한다.

#include<iostream>
#include<stack>
using namespace std;

bool map[50][50];
bool visited[50][50];

int T, M, N, K, x, y, answer;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

stack<pair<int,int>> st;
bool isIn(int y, int x);

int main(void)
{

    cin >> T;

    for (int t = 0; t < T; t++)
    {
        answer = 0;
        fill_n(&map[0][0], 50 * 50, false);
        fill_n(&visited[0][0], 50 * 50, false);

        cin >> M >> N >> K;
        for (int k = 0; k < K; k++) {
            cin >> x >> y;

            map[y][x] = true;
        }

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if(!visited[j][i] && map[j][i]) {
                    answer++;
                    st.push({j, i});
                    visited[j][i] = true;

                    while(!st.empty()) {
                        pair<int, int> elem = st.top();
                        st.pop();

                        for (int idx = 0; idx < 4; idx++) {
                            int ny = elem.first + dy[idx];
                            int nx = elem.second + dx[idx];

                            if(isIn(ny, nx) && !visited[ny][nx] && map[ny][nx]) {
                                visited[ny][nx] = true;
                                st.push({ny, nx});
                            }
                        }
                    }
                }
            }
        }

        cout << answer << "\n";
    }

    return 0;
}

bool isIn(int y, int x) {
    return (0 <= y && y < N) && (0 <= x && x < M);
}