[Silver 2] 1012번 유기농 배추

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

1012번: 유기농 배추

 

이 문제는 배열을 생성하고 DFS와 BFS를 사용해서 해결해야한다.

DFS를 한국어로 번역하면 깊이 우선 탐색이며, 이는 그래프 탐색 방법 중 하나이다.

또한 BFS는 너비 우선 탐색이다.

 

문제 풀이 방식은 다음과 같다.

1. 2차원 배열인 밭에 아무 것도 없게 초기화 한다.

2. 입력에 따라 배추를 심는다.

3. 2차원 배열을 순회하며 밭에 배추가 있고, 방문하지 않았던 좌표이면 DFS나 BFS를 진행한다.

 

BFS

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

class Point{
public:
    int x;
    int y;
    Point(int x, int y):x(x),y(y){}
};

int M, N, K;
int map[50][50] = { 0, }; // 밭
int visit[50][50] = { 0, }; // bfs를 위한 방문 배열 (밭과 크기가 같아야함)
int counter;

int dx[4] = { 1, 0, 0, -1 }; //오른쪽, 아래, 위, 왼쪽
int dy[4] = { 0, 1, -1, 0 }; //(dx, dy 배열에 있는 값이 인접 노드임, 따라서 BFS 성립)

void init() {
	counter = 0; 
    // N x M 만큼 밭과 방문 배열을 초기화
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			map[i][j] = 0;
			visit[i][j] = 0;
		}
	}
}

void bfs(int x, int y) {
	queue<Point> q;
    Point p(x,y); // 인자로 들어온 x와 y를 통해 시작 노드 생성

	q.push(p); // 시작 노드를 queue에 삽입
	visit[x][y] = 1; // 

	// BFS loop
	while (!q.empty()) {
		p = q.front(); // 큐에서 노드를 하나 꺼낸다.
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int tx = p.x + dx[i]; // 인접 노드 검사 
			int ty = p.y + dy[i];

			if (tx < 0 || tx >= M || ty < 0 || ty >= N) // 밭 밖에 나갔다면
				continue;
			if (map[tx][ty] == 0) // 벌레가 없다면
				continue;
			if (visit[tx][ty] == 1) // 이미 방문한 노드라면
				continue;

			visit[tx][ty] = 1; // 방문 표시
            Point tp(tx, ty); 
			q.push(tp); // 노드 삽입
		}
	}

}

int main(void) {

	int t;
	int x, y;
	cin >> t;

	while (t > 0) {
		cin >> M >> N >> K;
		init();
		for (int i = 0; i < K; i++) {
			cin >> x >> y;
			map[x][y] = 1;
		}
		for (int i = 0; i < M; i++) { // M 까지 반복
			for (int j = 0; j < N; j++) { // N 까지 반복
				if (visit[i][j] == 0 && map[i][j] == 1){
					bfs(i, j); 
					counter++;
				}
			}
		}
		cout << counter << endl;
		t--;
	}

	return 0;
}

BFS에 대한 상세한 설명

https://hanseongbugi2study.tistory.com/36

<algorithm> 너비 우선 탐색(BFS)

 

DFS

#include <iostream>
using namespace std;
 
int T, M, N, K;
int map[51][51];
int visited[51][51];
int dy[] = {0,0,-1,1};
int dx[] = {-1,1,0,0};
 
void reset() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            map[i][j] = 0;
        }
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            visited[i][j] = 0;
        }
    }
}
 
void DFS(int y, int x) {
    visited[y][x] = 1;
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || nx >= M || ny < 0 || ny >= N)
            continue;
        
        if (map[ny][nx] == 1 && visited[ny][nx] == 0) {
            DFS(ny, nx);
        }
    }
}
 
int main() {
    cin >> T;
 
    while (T--) {
        cin >> M >> N >> K;
 
        reset();
 
        while (K--) {
            int x, y;
            cin >> x >> y;
            map[y][x] = 1;
        }
 
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1 && visited[i][j] == 0) {
                    DFS(i, j);
                    cnt++;
                }
            }
        }
 
        cout << cnt << endl;
    }
 
}