[코딩테스트 C++] 유기농 배추

오늘의 문제

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

유기농 배추

접근 법

• 배추가 있는영역의 개수를 출력하면 된다.
• 1초에 MAX가 50이어서 N^3도 가능하다 최단거리 찾는거였다면 플로이드와샬도 가능
• BFS를 연습하기 위해 BFS를 이용했다. DFS로도 풀 수 있다.
• true인 곳을 모두 False로 바꾼다.

나의 풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int t, m, n, k; // 가로, 세로
const int MAX = 50;
bool field[MAX][MAX] = {false, };
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
queue<pair<int, int>> q;

// 유기농 배추
void solution(int a, int b){
    q.push(make_pair(a, b));
    field[a][b] = false;
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int moveX = x+dx[i];
            int moveY = y+dy[i];
            if(moveX>=m || moveX<0 || moveY>=n || moveY<0)
                continue;
            if(field[moveY][moveX] == true){
                field[moveY][moveX] = false;
                q.push(make_pair(moveY, moveX));
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin>>t;
    int a, b;
    for(int i=0;i<t;i++){
        cin>> m >>n >>k;
        for(int j =0 ;j<k;j++){
            cin>>a >>b;
            field[b][a] = true;
        }
        int answer = 0;
        for(a = 0;a<n;a++){
            for(b = 0;b<m;b++){
                if(field[a][b] == true){
                    answer++;
                    solution(a, b);
                }
            }
        }
        cout<<answer<<endl;
    }
    return 0;
}

다른 풀이

#include <stdio.h>
#include <memory.h>

const int dx[] = { 0,0,-1,1 };
const int dy[] = { -1,1,0,0 };

int tc, n, m, k, i, j, x, y, ans;
bool farm[52][52];

void dfs(int x, int y) {
	farm[x][y] = 0;
	for (int i = 0; i < 4; i++)
		if (farm[x + dx[i]][y + dy[i]]) dfs(x + dx[i], y + dy[i]);
}

int main() {
	scanf("%d", &tc);

	while (tc--) {
		ans = 0, memset(farm, 0, sizeof(farm));
		scanf("%d %d %d", &n, &m, &k);
		while (k--) {
			scanf("%d %d", &x, &y);
			farm[++x][++y] = 1;
		}
		for (i = 1; i <= n; i++)
			for (j = 1; j <= m; j++)
				if (farm[i][j]) ans++, dfs(i, j);
		printf("%d\n", ans);
	}

	return 0;
}

배울 점

• DFS로 깔끔하게 잘 짜내셨다.