[모의 테스트 풀이] 유기농 배추

www.acmicpc.net/problem/1012

1012번: 유기농 배추

드디어 마지막 문제 풀이입니다!

고생 많으셨어요!

 

이 문제는 탐색 문제입니다. 이번 포스팅에서는 bfs탐색으로 같이 풀어보겠습니다.

 

이러한 xy좌표가 있는 문제는 풀이 과정이 거의 비슷한 것 같습니다. 깊이 우선 탐색과 너비 우선 탐색은 잘 알고 있다고 가정하고, 어떻게 이 알고리즘들이 적용되었는지 먼저 코드를 보면서 살펴보겠습니다.

 

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

int field[51][51];
int visited[51][51];
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
int n, m, k;
queue<pair <int, int> > q;

void input(int n, int m, int k);
void bfs(int cnt);

int main()
{
	ios_base::sync_with_stdio(0);
	int t;
	cin >> t;
	while (t--)
	{
		int cnt = 0;
		cin >> n >> m >> k;
		input(n, m, k);
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (field[i][j] == 1 && visited[i][j] == 0)
				{
					q.push(make_pair(i, j));
					bfs(cnt++);
				}
			}
		}
		cout << cnt << '\n';
	}
}

void input(int n, int m, int k)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			field[i][j] = 0;
			visited[i][j] = 0;
		}
	}
	while (k--)
	{
		int x, y;
		cin >> x >> y;
		field[x][y] = 1;
	}
}

void bfs(int cnt)
{
	field[q.front().first][q.front().second] = cnt;
	visited[q.front().first][q.front().second] = 1;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++)
		{
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (0 <= nx && nx <= n && 0 <= ny && ny <= m)
			{
				if (visited[nx][ny] == 0 && field[nx][ny] != 0)
				{
					q.push(make_pair(nx, ny));
					visited[nx][ny] = 1;
					field[nx][ny] = cnt;
				}
			}
		}
	}

}

 

코드가 참 복잡해 보입니다. 탐색문제들을 풀다보면 bfs dfs탐색 부분에서 이런 식의 탐색이 겹치는 부분들이 참 많습니다. 그러다가 이 알고리즘의 참맛을 느껴버릴 수도 있습니다. 

 

자! 그럼 한번 찬찬히 살펴볼까요?

요 부분은 입력 조건이 어려워서 따로 함수로 입력부분을 뺀 모습을 보여줍니다.

field와 visited를 0으로 초기화 해주고, 입력을 받아 field의 x, y좌표에 배추벌레를 입력해주는 모습을 볼 수 있습니다.

visited는 다음 코드를 보면서 어떤 역할을 하는지 살펴보겠습니다.

 

(사진 2) bfs를 호출하기 전 모습. field[i][j]가 1이고, 아직 방문하지 않았다면, queue에 (i, j) 좌표를 추가하여 bfs를 시작합니다.

사진 3

참 복잡하네요. 60, 61번째 줄부터 다음 예시를 보면서 이해해봅시다.

 

0	0	0	0
0	1	1	0
0	0	1	0
0	0	0	0

다음과 같은 필드에 배추벌레가 심어져 있습니다. 사진 2에서 탐색을 통해 처음 발견한 배추 흰 벌레는 위 표에서 빨간 색으로 색칠한 부분과 같습니다. 이 부분의 좌표는 (1, 1)입니다. 먼저 queue에 이 좌표를 넣고, bfs를 시작합니다. 

 

[bfs 시작 부분]

줄	설명
60	field를 1과 다른 숫자로 세팅하여 나중에 다시 방문하지 않도록 합니다.
61	visited를 1로 세팅하여 방문했음을 표시합니다.
64 ~ 65	queue의 맨 앞의 원소를 x, y로 설정합니다.
67	x,y 좌표를 기준으로 사방 탐색을 시작합니다. 원 코드의 전역변수로 설정한 dx와 dy를 보면 왜 이렇게 해야함 하는지 이해하기 쉽습니다.
69 ~ 70	새로 움직일 좌표를 nx, ny로 설정합니다.
71	nx, ny가 필드를 벗어나지 않도록 경계를 설정합니다.
73 ~ 77	해당 좌표가 0이 아니고 방문하지도 않았다면, queue에 새로운 위치를 저장하고, 방문표시 및 field에도 표시를 해줍니다.

이 알고리즘은 queue가 다 빌때까지 반복됩니다. queue에 좌표들을 계속 기억하면서 진행되고, 길이 막혔을 경우 기억한 좌표들을 기준으로 다시 탐색을 시작하므로, 결국 배추 흰 지렁이가 있는 모든 좌표들을 방문할 수 있게 됩니다.