[백준/C++] 1012. 유기농 배추

알고리즘 학회 과제이다. 내 제출 보니까 bfs로 풀었어서 이번엔 dfs로 풀어봤다.

1012. 유기농배추

밭을 샅샅이 뒤지면서 배추가 심어져있는 좌표 중 방문하지 않은 노드로 dfs를 호출한다. 한 번 돌고 오면 배추가 심어진 동네(?)는 다 돌고 온 것이기 때문에 count++을 해준다.

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

bool visited[51][51];
int field[51][51];
int prow[4] = { -1, 0, 1, 0 };
int pcol[4] = { 0, 1, 0, -1 };
int t, n, m, k;

void dfs(int x, int y){
    visited[x][y] = true;

    for(int i = 0; i<4; i++){
        int nx = x + prow[i];
        int ny = y + pcol[i];
        if(nx >= 0 && nx<=m && ny>=0 && ny<=n && field[nx][ny] == 1){
            if(!visited[nx][ny]){
                //cout<<nx<<" "<<ny<<endl;
                dfs(nx, ny);
            }
        }
    }
}

int main(){
    cin>>t;

    while(t--){
        cin>>m>>n>>k;
        int row, col;
        int count = 0;
        for(int i = 0; i<k; i++){
            cin>>row>>col;
            field[row][col] = 1;
        }

        for(int i = 0; i<m; i++){
            for(int j = 0; j<n; j++){
                if((field[i][j] == 1) && !visited[i][j]){
                    count++;
                    dfs(i, j);
                }
                //cout<<"("<<i<<", "<<j<<")"<<endl;
            }
        }

        cout<<count<<endl;
        memset(visited, false, sizeof(visited));
        memset(field, 0, sizeof(field));
    }
}

추가로 예전에 풀었던 bfs 방식도 넣어주자!
이거 보면서 무서웠던 게 그 때나 지금이나 변수 이름 짓거나 시계방향으로 주변 탐색하는 건 그대로다... 비슷한 토마토 문제도 내 풀이 들어가서 봤는데 그때도 여전히 시계방향으로 돌았다. 처음부터 변수 이름 잘 짓는 습관을 들이는 게 좋은 것 같다!

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int field[51][51] = {0, };
bool c[51][51] = {0, };
int prow[4] = { -1, 0, 1, 0 };
int pcol[4] = { 0, 1, 0, -1 };
queue <pair<int, int>> q;
int t, n, m, k;

void bfs(int x, int y){
	c[x][y] = 1;
	q.push({x, y});

	while(!q.empty()){
		int x1 = q.front().first;
		int y1 = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int x2 = x1 + prow[i];
			int y2 = y1 + pcol[i];

			if (x2 >= 0 && x2 < m && y2 >= 0 && y2 < n && field[x2][y2] == 1 && c[x2][y2] == 0) {
				q.push({ x2, y2 });
				c[x2][y2] = 1;
				
			}
		}
	}
}

int main() {
 
  cin>>t;

  while(t--){
	  cin>>m>>n>>k;
	  int count = 0;
	  memset(c,0,sizeof(c));
	  memset(field,0,sizeof(field));

	  for(int i = 0; i<k; i++){
		  int x, y;
		  cin>>x>>y;
		  field[x][y] = 1;
	  }

	  for(int i = 0; i<m; i++){
		  for(int j = 0; j<n; j++){
			  if(field[i][j] == 1 && c[i][j] == 0){
				bfs(i, j);
			  	count++;
			  }
		  }
	  }
	  cout<<count<<"\n";
  }
}