백준 1012

1. 문제분석

심어져 있는 배추(1)를 모두 해충으로 부터 보호하기 위해서 몇 마리의 지렁이가 필요한지 구하는 문제

시간제한은 1초로 50*50 = 2,500 최대 연산을 수행해도 CPU는 1초당 대략 1억번 연산을 수행한다고 가정했을 때 이중 for문 O(n*n) 알고리즘으로 풀어도 됨

 

로직)

1. 이차원 배열의 크기만큼 이중 for문을 돌면서 첫번째 배추의 위치를 큐에 넣음

-> dist[](방문표시) 배열에 1을 넣어서 방문여부를 남김, 지렁이 개수를 1증가

-> 상하좌우로 인접한 배추가 있는지 체크

 --> 인접한 배추가 있으면 dist[](방문표시) 배열에 1을 넣어서 방문여부를 남김

 

2. 큐가 비게되면 이중 for문을 다시 돌면서 dist(방문표시)가 0이면서 배추가 있는지 확인

-> 새로운 구역에 지렁이가 스며들지 않은 배추가 있다면 1번 문장을 수행 

-> 더이상 없다면 지렁이 개수를 출력하고 프로그램 종료

 

2. 코드

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

int board[50][50];
int dist[50][50];

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


int main(void) {
	
	int T, M, N, K; // M(가로), N(세로)
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> M >> N >> K;

		// board, dist 초기화
		// 배열 -> N(세로, 아래쪽), M(가로, 옆쪽)
		for (int X = 0; X < N; X++) {
			for (int Y = 0; Y < M; Y++) {
				board[X][Y] = 0;
				dist[X][Y] = 0;
			}
		}

		// 문제에서는 가로, 세로 순으로 입력받는데 
		// 배열에 들어갈 때는 가로가 두번째 인덱스로 들어가고 세로가 첫번째 인덱스로 들어가야 됨 ** 
		for (int j = 0; j < K; j++) {
			int y, x;
			cin >> y >> x;
			board[x][y] = 1;
		}
		
		int earthwormCnt = 0;
		for (int row = 0; row < N; row++) {
			for (int col = 0; col < M; col++) {
				if (board[row][col] == 1 && dist[row][col] == 0) {
					queue<pair<int, int>> Q;
					earthwormCnt++;
					dist[row][col] = 1;
					Q.push({ row, col });
					while (!Q.empty()) {
						pair<int, int> cur = Q.front(); Q.pop();
						for (int dir = 0; dir < 4; dir++) {
							int nx = cur.first + dx[dir];
							int ny = cur.second + dy[dir];
							if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
							if (board[nx][ny] == 1 && dist[nx][ny] == 0) {
								dist[nx][ny] = 1;
								Q.push({ nx, ny });
							}
						}
					}
				}
			}
		}
		cout << earthwormCnt << "\n";

	}


	return 0;
}

 

 

재풀이 코드

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

int board[52][52]; // 배추밭
bool vis[52][52];    // 흰지렁이가 방문한 배추 위치
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int m, n, k;

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	// 1.입력
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> m >> n >> k;

		int posX, posY;
		for (int j = 0; j < k; j++) {			
			cin >> posX >> posY;
			board[posY][posX] = 1;
		}

		// 2.로직
		int earthwormCount = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (board[i][j] == 1 && vis[i][j] == false) {
					earthwormCount++;
					vis[i][j] = 1;
					queue<pair<int, int>> Q;
					Q.push({ i,j });

					while (!Q.empty()) {
						pair<int, int> cur = Q.front(); Q.pop();
						for (int dir = 0; dir < 4; dir++) {
							int nx = cur.first + dx[dir];
							int ny = cur.second + dy[dir];
							if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
							if (vis[nx][ny] == 1 || board[nx][ny] == 0) continue;
							vis[nx][ny] = 1;
							Q.push({ nx, ny });
						}
					}
				}
			}
		}
		cout << earthwormCount << "\n"; // 출력
		// board, vis 배열 초기화
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				board[i][j] = 0;
				vis[i][j] = false;
			}
		}
	}				
		
	return 0;
}

 

가로랑 세로 크기를 이차원 배열상으로 변경했을 때 어떤식으로 되는지 헷갈리기 때문에 이 점을 중요하게 확인해야 함