[BOJ 13269 // C++] 쌓기나무

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 13269번 문제인 쌓기나무이다.
문제는 아래 링크를 확인하자.

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

13269번: 쌓기나무

 

먼저 위에서 보았을 때 쌓기나무가 존재하는 각 칸에 가능한 많은 쌓기나무, 즉 해당 칸의 행과 열에서 볼 수 있는 쌓기나무 의 수 중 작은 값만큼의 쌓기나무를 놓아보자. 만약 이렇게 놓은 쌓기나무의 배치가 유효한 배치라면 이것이 문제에서 찾고자 하는 배치임은 자명하다. 더 많은 쌓기나무를 놓을 수 있는 방법이 없다는 것이 자명하기 때문이다.

 

이 배치가 유효하지 않은 경우, 그 이유는 다음과 같은 세 가지로 나눌 수 있다.

 

(1) 위에서 보았을 때 쌓기나무가 존재해야 하지만 위와 같은 과정에서 해당 칸에 놓은 쌓기나무의 수가 0개인 경우

이 경우 어떻게 하더라도 그 칸에 쌓기나무를 놓을 수 없으므로 -1을 출력해야 한다.

 

(2) 어떤 행에 그 행에서 볼 수 있어야 하는 쌓기나무의 수만큼 쌓기나무가 쌓인 칸이 없는 경우

이 경우 어떻게 하더라도 그 행에 원하는 개수의 쌓기나무를 놓을 수 있는 칸이 없으므로 -1을 출력해야 한다.

 

(3) 어떤 열에 그 열에서 볼 수 있어야 하는 쌓기나무의 수만큼 쌓기나무가 쌓인 칸이 없는 경우

2에서 행이 열로 바뀐 경우이다. 같은 이유로 -1을 출력해야 한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int R, C;
int arr[500][500];
int hR[500], hC[500], mxR[500], mxC[500];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> arr[r][c];
		}
	}

	for (int c = 0; c < C; c++) cin >> hC[c];
	for (int r = R - 1; r > -1; r--) cin >> hR[r];

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (arr[r][c]) {
				if (hR[r] == 0 || hC[c] == 0) {
					cout << -1;
					return 0;
				}
				arr[r][c] = min(hR[r], hC[c]);
				mxR[r] = max(mxR[r], arr[r][c]);
				mxC[c] = max(mxC[c], arr[r][c]);
			}
		}
	}

	for (int r = 0; r < R; r++) {
		if (mxR[r] != hR[r]) {
			cout << -1;
			return 0;
		}
	}
	for (int c = 0; c < C; c++) {
		if (mxC[c] != hC[c]) {
			cout << -1;
			return 0;
		}
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cout << arr[r][c] << ' ';
		}
		cout << '\n';
	}
}