[BOJ] 1012번 : 유기농 배추

1. problem :

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std; 

#define X first 
#define Y second 
int board[52][52]; 
int vis[52][52]; 
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int T, row, col, K; // test case 수, 세로, 가로, 배추 갯수;  

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> T;
	while (T--) {
		memset(board, 0, sizeof(board)); // 배열 초기화
		memset(vis, 0, sizeof(vis));
		int ans = 0; 
		cin >> col >> row >> K; 
		for (int i = 0; i < K; i++) { // board에 상추 위치 기록
			int y,x ;
			cin >> x >> y;  // 열 --> 행
			board[y][x] = 1; 
		}
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (board[i][j] != 1 || vis[i][j] != 0) continue;
				queue<pair<int, int>> Q; 
				ans++;
				Q.push({ i,j }); 
				vis[i][j] = 1;
				while (!Q.empty()) {
					pair<int, int> cur = Q.front(); Q.pop(); 
					for (int dir = 0; dir < 4; dir++) {
						int nx = cur.X + dx[dir];
						int ny = cur.Y + dy[dir]; 
						if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
						if (vis[nx][ny] != 0 || board[nx][ny] != 1) continue; 
						vis[nx][ny] = 1; 
						Q.push({ nx,ny });
					}
				}
			}
		}
		cout << ans << '\n';
	}
}

memset을 이용한 배열을 초기화해 주는 것을 놓쳤다. C6262경고가 떴다. 이 경고는 stack overflow라고 한다. 해결법은 나중에 알아봐야겠다. 

 

3. solution 2 :

#include <bits/stdc++.h>
using namespace std; 

#define X first 
#define Y second 
int board[52][52]; 
int vis[52][52]; 
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int T, row, col, K; // test case 수, 세로, 가로, 배추 갯수;  
queue<pair<int, int>> Q;
void bfs(int x, int y) {
	Q.push({ x,y });
	vis[x][y] = 1;
	while (!Q.empty()) {
		pair<int, int> cur = Q.front(); Q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
			if (vis[nx][ny] != 0 || board[nx][ny] != 1) continue;
			vis[nx][ny] = 1;
			Q.push({ nx,ny });
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> T;
	while (T--) {
		int ans = 0; 
		cin >> col >> row >> K; 
		for (int i = 0; i < K; i++) { // board에 상추 위치 기록
			int y,x ;
			cin >> x >> y;  // 열 --> 행
			board[y][x] = 1; 
		}
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (board[i][j] != 1 || vis[i][j] != 0) continue;
				ans++;
				bfs(i, j);
			}
		}
		for (int i = 0; i < row; i++) {
			fill(board[i], board[i] + col, 0);
			fill(vis[i], vis[i] + col, 0);
		}
		cout << ans << '\n';
	}
}

<source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/solutions/1012.cpp > 

이렇게 1을 발견하고 나서 Q.push를 하는 부분부터의 logic을 bfs라는 함수를 만들어서 빼면 main에 warning이 사라진다. 

그리고  이 solution은 memset대신 fill이라는 함수로 초기화를 시킨다.