[백준/C++] 1012번. 유기농 배추

문제

1012번: 유기농 배추

---

1. 첫 번째 풀이

사고 과정

- 알고리즘 수업 초기에 풀었던 종류의 문제.

- 입력에 맞춰 밭을 생성

- 모든 칸을 순회, 1인 경우 탐색을 진행

- 0이면 종료, 1이면 해당 칸을 2로 수정하고 반복.

- 칸의 크기가 아닌 집합의 개수를 세야 하므로, 탐색이 끝난 후 전체 count를 1 증가시키는 식으로 작성

 

1. 각 입력에 따른 반복문 설정

2. 재귀 함수를 사용, 인접한 모든 1을 2로 칠하는 함수 작성

3. 모든 칸을 순회, 해당 칸이 1이라면 count를 1 증가시키고 인접 배추를 모두 2로 칠함

 

코드

#include <iostream>
#include <vector>

int T, M, N, K, posX, posY;
std::vector<std::vector<int>> patch;

// (x, y)부터 인접한 셀들을 2로 칠하는 함수
void paintCells(int x, int y) {
	if (x < 0 || y < 0 || x >= M || y >= N || patch[y][x] != 1) {
		return;
	}

	patch[y][x] = 2;

	paintCells(x, y - 1);
	paintCells(x + 1, y);
	paintCells(x, y + 1);
	paintCells(x - 1, y);
	
	return;
}

int main() {
	std::cin >> T;

	// T번 반복
	for (int i = 0; i < T; i++) {
		int count = 0;
		std::cin >> M >> N >> K;
		// 밭 초기화
		patch.resize(N, std::vector<int>(M, 0));

		// 배추 생성
		for (int j = 0; j < K; j++) {
			std::cin >> posX >> posY;
			patch[posY][posX] = 1;
		}

		// 전체 밭 순회 (x는 세로 방향, y는 가로 방향)
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (patch[y][x] == 1) {
					count++;
					paintCells(x, y);
				}
			}
		}

		std::cout << count << '\n';
	}


	return 0;
}

 

결과

비주얼 스튜디오에선 잘 됐는데, 백준에 제출하니 OutOfBounds 에러가 떴다.

---

2. 마지막 풀이

사고 과정

- OutOfBounds 에러는 벡터의 범위를 초과해서 나타난 에러다.

- 벡터에 접근하는 문장은 단 셋 뿐인데, 처음 밭을 만들고 배추를 심을 때, 모든 칸을 순회하며 해당 칸이 1인지 검사할 때, 그리고 paintCells 내부에서 칸이 1이 아닌지 검사할 때다.

- 첫 번째 경우, 0 < y < N, 0 < x < M이므로 배열 범위를 벗어나는 일은 없어 보인다.

- 혹시나 싶어 비주얼 스튜디오에서 if (patch[x][y] == 1)로 접근해 봤지만, 바로 OutOfRange 에러가 발생했다. 즉 이 부분엔 문제가 없다.

- 백준에 paintCells 명령어를 지우고 제출해 봤다. 그럼에도 OutOfBounds 에러가 떴다.

- return 0를 이용해 밭 생성 후 프로그램을 끊어봤다. 이번엔 에러가 뜨지 않고 틀렸습니다! 가 나왔다. 즉 posX, posY를 받아와 배추를 심는 과정엔 문제가 없다.

- 이후 다양한 변화를 주다가, 아예 배열 순회 부분을 통째로 날려보았다. 즉, 밭을 생성하는 부분만 남겨두었다. 이번에도 OutOfBounds 에러가 떴다. (아까 return으로 끊을 땐 잘 되더니?)

- 백준에 계속 제출하며 얻은 결과를 정리해 보면, patch 배열에 직접 접근한 모든 코드에서 에러가 떴다.

- 비주얼 스튜디오에선 아무 에러 없이 잘 돌아가는데, 백준에만 제출하면 에러가 뜨니 참 골치 아프다.

- 답답한 나머지 chatGPT에게 코드를 보여주며 물어보았다. 그러나 chatGPT도 문제를 파악하지 못 했다. 이미 멀쩡한 부분을 수정본이랍시고 답변해 주는 게 전부였다.

- 애초에 유동적으로 크기를 변경하려던 게 문제일 수도 있다. 이번엔 배열을 이용해 문제를 풀어보았다.

 

코드

#include <iostream>

int T, M, N, K, posX, posY;
int patch[51][51];

void paintCells(int x, int y) {
	if (x < 0 || x >= M || y < 0 || y >= N || patch[y][x] != 1) {
		return;
	}

	patch[y][x] = 2;

	paintCells(x, y - 1);
	paintCells(x + 1, y);
	paintCells(x, y + 1);
	paintCells(x - 1, y);
	
	return;
}

int main() {
	std::cin >> T;

	for (int i = 0; i < T; i++) {
		int count = 0;
		std::cin >> M >> N >> K;

		for (int j = 0; j < K; j++) {
			std::cin >> posX >> posY;
			patch[posY][posX] = 1;
		}

		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (patch[y][x] == 1) {
					count++;
					paintCells(x, y);
				}
			}
		}

		std::cout << count << '\n';
	}

	return 0;
}

 

결과

... 성공이다. 핵심 로직은 바뀐 게 없고, 그저 vector를 array로 변경하고, 넉넉하게 51씩 할당해준게 전부인데 말이다. 살짝 허탈했다.

---

개선

실험 1

- 만약 크기가 유동적으로 변하는 게 문제였다면, 벡터를 쓰고 크기를 고정시키면 성공할까?

 

코드

#include <iostream>
#include <vector>

int T, M, N, K, posX, posY;
std::vector<std::vector<int>> patch(51, std::vector<int>(51, 0));

void paintCells(int x, int y) {
	if (x < 0 || x >= M || y < 0 || y >= N || patch[y][x] != 1) {
		return;
	}

	patch[y][x] = 2;

	paintCells(x, y - 1);
	paintCells(x + 1, y);
	paintCells(x, y + 1);
	paintCells(x - 1, y);
	
	return;
}

int main() {
	std::cin >> T;

	for (int i = 0; i < T; i++) {
		int count = 0;
		std::cin >> M >> N >> K;

		for (int j = 0; j < K; j++) {
			std::cin >> posX >> posY;
			patch[posY][posX] = 1;
		}

		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (patch[y][] == 1) {
					count++;
					paintCells(x, y);
				}
			}
		}

		std::cout << count << '\n';
	}

	return 0;
}

 

결과

성공. 즉 벡터냐 배열이냐는 중요하지 않고, 동적으로 크기를 변경하는 과정에서 에러가 생긴 듯하다.

---

실험 2

- M, N을 받아온 후 순서를 잘못 지정해준 걸까?

 

코드

#include <iostream>
#include <vector>

int T, M, N, K, posX, posY;
std::vector<std::vector<int>> patch;

void paintCells(int x, int y) {
	if (x < 0 || x >= M || y < 0 || y >= N || patch[y][x] != 1) {
		return;
	}

	patch[y][x] = 2;

	paintCells(x, y - 1);
	paintCells(x + 1, y);
	paintCells(x, y + 1);
	paintCells(x - 1, y);
	
	return;
}

int main() {
	std::cin >> T;

	for (int i = 0; i < T; i++) {
		int count = 0;
		std::cin >> M >> N >> K;
		patch.resize(M, std::vector<int>(N, 0));

		for (int j = 0; j < K; j++) {
			std::cin >> posX >> posY;
			patch[posY][posX] = 1;
		}

		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (patch[y][x] == 1) {
					count++;
					paintCells(x, y);
				}
			}
		}

		std::cout << count << '\n';
	}

	return 0;
}

 

결과

백준까지 갈 필요도 없다. 당연히 에러가 난다.

---

실험 3

- resize 함수에 문제가 있었던 걸까?

사고 과정

- 먼저 resize 함수에 대해 다시 알아보았다.

- resize는 벡터의 원소 수를 조절하는 함수이며, 할당된 크기는 변하지 않는다. 흔히 reserve와 자주 비교된다.

- 벡터는 capacity와 size가 존재하는데, size는 실제 원소의 개수, capacity는 벡터를 위해 할당된 메모리 크기를 뜻한다.

- 만약 원소 100개분 메모리를 벡터에 할당해주고, 거기에 10개의 원소를 채웠다면, capacity = 100, size = 10이 되는 것이다.

- resize는 오직 size에만 관여하며, capacity는 건들지 않는다. capacity는 reserve 함수를 통해 지정할 수 있다.

- 그래서 다시 공부해봐도 문제는 없어 보이는데, 일단 reserve 함수를 같이 써서 capacity도 맞춰 보았다.

 

코드

#include <iostream>
#include <vector>

int T, M, N, K, posX, posY;
std::vector<std::vector<int>> patch;

void paintCells(int x, int y) {
	if (x < 0 || x >= M || y < 0 || y >= N || patch[y][x] != 1) {
		return;
	}

	patch[y][x] = 2;

	paintCells(x, y - 1);
	paintCells(x + 1, y);
	paintCells(x, y + 1);
	paintCells(x - 1, y);
	
	return;
}

int main() {
	std::cin >> T;

	for (int i = 0; i < T; i++) {
		int count = 0;
		std::cin >> M >> N >> K;
		patch.reserve(N);
		patch.resize(N, std::vector<int>(M, 0));

		for (int j = 0; j < K; j++) {
			std::cin >> posX >> posY;
			patch[posY][posX] = 1;
		}

		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (patch[y][x] == 1) {
					count++;
					paintCells(x, y);
				}
			}
		}

		std::cout << count << '\n';
	}

	return 0;
}

 

결과

런타임 에러. 함수 자체의 문제는 아닌 것 같다.

---

실험 4

- resize 크기가 잘못된 걸까?

사고 과정

- 만약 배열의 크기가 N, M보다 더 커야했던 건 아닐까?

 

코드

#include <iostream>
#include <vector>

int T, M, N, K, posX, posY;
std::vector<std::vector<int>> patch;

void paintCells(int x, int y) {
	if (x < 0 || x >= M || y < 0 || y >= N || patch[y][x] != 1) {
		return;
	}

	patch[y][x] = 2;

	paintCells(x, y - 1);
	paintCells(x + 1, y);
	paintCells(x, y + 1);
	paintCells(x - 1, y);
	
	return;
}

int main() {
	std::cin >> T;

	for (int i = 0; i < T; i++) {
		int count = 0;
		std::cin >> M >> N >> K;
		patch.resize(N + 1, std::vector<int>(M + 1, 0));

		for (int j = 0; j < K; j++) {
			std::cin >> posX >> posY;
			patch[posY][posX] = 1;
		}

		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (patch[y][x] == 1) {
					count++;
					paintCells(x, y);
				}
			}
		}

		std::cout << count << '\n';
	}

	return 0;
}

 

결과

... 딱히 그것도 아닌 것 같다. 혹시 1은 너무 작은가 싶어 10을 더해봤는데도 결과는 같았다.

 

결국 배열 크기 동적 할당에 문제가 있다는 것만 알아냈을 뿐, 더 자세한 이유는 알아내지 못 했다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/20014077

bm1387님의 코드. 열람 가능한 C++ 코드 중 순위가 가장 높아 가져왔는데, 사실상 C라고 보는 게 맞는 것 같기도 하다.

내 코드와 비교

- 로직은 완벽하게 똑같다.

- 가로세로 51칸인 배열로 고정하고 시작하셨다.

- 재귀함수에서, x, y가 M, N보다 큰 경우는 고려하지 않으셨다.

- 굳이 새 수인 2로 설정하는 대신, 아예 0으로 밀어버리셨다. 이렇게 되면 비트나 bool로 구현하여 메모리를 절약할 수도 있을 것이다.

- T번 반복하는 내부 로직도 별도의 함수로 분리하셨다.

- cnt를 각 for문에 재사용하셨다. 밭에 배추를 심는 반복문과, 모든 칸을 순회하며 인접 배추를 찾는 반복문은 완전 별도이기에 재사용해도 된다.

---

강평

로직에 문제가 없어서 왠지 화나는 문제. 아예 해결 방법을 잘못짚었다면 "이 단서로 이렇게 접근했어야 했는데!"라고 배워갔을 텐데, 이번엔 삽질을 좀 많이 했다.

VS에선 멀쩡하고 백준에서만 나타나는 버그를 잡기 위한 흔적들

그럼에도 아직 완전히 공부하지 못 했다. 왜 벡터 크기를 동적으로 설정했을 때 에러가 뜬 건지, 더 공부해서 반드시 알아내겠다.