[백준] 1012-유기농 배추(C++)

문제 링크:https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

dfs, bfs 를 사용하는 완전 탐색 문제였습니다. 

1인 위치의 상하좌우를 이동하며 해당위치가 1인지, 방문 한적 있는지 판단하는 문제였습니다.

bfs 보다는 dfs 로 구현하는게 좋은 문제였습니다.

 

 

저는 큐를 탐색하는 형태인 bfs로 탐색하며 dfs를 추가로 사용해서 구현하였습니다.

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

int t = 0, k = 0, m = 0, n = 0;
int	arr[51][51];
bool visited[51][51];
int que[2500][2];
int started = 0, ended = 0;
int result = 0;

int x_ar[4] = { -1,1,0,0 };
int y_ar[4] = { 0,0,1,-1 };
void dfs(int y, int x);
void bfs() {

	while (started != ended) {
		
		int x = que[started][0];
		int y = que[started++][1];
		if (visited[y][x] == 1) continue;
		
		result++;

		dfs(y, x);

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

	for (int i = 0; i < 4; i++) {
		int yy = y + y_ar[i];
		int xx = x + x_ar[i];
		if (yy >= 0 && yy < n && xx >= 0 && xx < m) {
			if(arr[yy][xx] == 1 &&visited[yy][xx] == 0)
				dfs(yy, xx);
		}
	}

}

int main() {

	cin >> t;

	while (t--) {

		cin >> m >> n >> k;
		started = 0, ended = 0;
		result = 0;
		memset(arr, 0, sizeof(arr));
		memset(que, 0, sizeof(que));
		memset(visited, 0, sizeof(visited));
		int x, y;

		for (int i = 0; i < k; i++) {
			cin >> que[ended][0] >> que[ended][1];
			arr[que[ended][1]][que[ended][0]] = 1;
			ended++;

		}
		
		bfs();
		
		cout << result << endl;
	}
}

 

 

 

더욱 최적화 된 코드입니다.

다시 풀어본 문제인데, 1년전에 풀었던 코드가 훨씬 효율이 좋아서 현타가 왔습니다... 

굳이 큐를 사용할 필요 없는 문제였습니다. ( 위의 코드는 사실 큐라고 하기에도 애매한 배열의 사용형태입니다..)

#include <iostream>
#include <string.h>
using namespace std;
 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
int M,N,K;
int arr[50][50]={0};
int visited[50][50]={0};
 
void dfs(int y,int x){
    
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        
        if(ny<0 || ny>=N || nx<0 || nx>=M)
            continue;
        
        if(arr[ny][nx] && !visited[ny][nx]){
            visited[ny][nx]++;
            dfs(ny,nx);
        }
    }
}
int main(){
    int T,x,y;
    cin>>T;
    
    for(int testCase=0;testCase<T;testCase++){
        scanf("%d %d %d",&M,&N,&K);
        
        memset(arr,0,sizeof(arr));
        memset(visited,0,sizeof(visited));
        
        int ans=0; //지렁이 개수
        
        for(int i=0;i<K;i++){
            scanf("%d %d",&x,&y);
            arr[y][x]=1;
        }
        
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
                if(arr[i][j] && !visited[i][j]){
                    
                    ans++;
                    visited[i][j]++;
                    dfs(i,j);
                    
                }
        
        cout<<ans<<endl;
    }
    return 0;
}

 

꼭 직접 작성하면서 풀어보세요! 화이팅 :)