[백준 C++] 24727 인지융~

2022 연세대학교 신학기맞이 프로그래밍 경진대회 Open Contest E번 문제였다.

문제

연세대학교는 2022년부터 인공지능융합대학이라는 단과대를 새로 만들고, 기존 공과대학 소속이었던 컴퓨터과학과를 해당 단과대로 보내버렸다. 하지만 아직 인공지능융합대학 건물이 지어지지 않았기 때문에, 학생들은 여전히 공학관을 사용하고 있다.

이에 공과대학의 다른 학과 학생들이 컴퓨터과학과 학생들을 놀리기 시작했다!

화가 난 컴퓨터과학과 학생들은 바리케이드를 쳐 다른 공과대학 학생들이 접근하지 못하게 하였다. 하지만 실수로 다른 학과의 공간을 침범해 버려, 성난 학생들과 교수님들이 바리케이드를 부숴버렸다!

결국 긴 시간의 협상 끝에, 공과대학 측이 필요한 공간의 크기와 컴퓨터과학과가 필요한 공간의 크기를 미리 제출한 후, 각각 크기를 보장하면서 바리케이드를 치기로 합의하였다.

공학관은 $N \times N$ 크기의 정사각형 모양이고, 바리케이드를 친 이후 컴퓨터과학과의 공간과 공과대학 측의 공간은 연결되어 있지 않아야 하나, 각자의 공간은 모두 연결되어 있어야 한다.

여기서 "연결"이라 함은, 어떤 공간이 상하좌우로 인접해 있는 것을 말한다.

예를 들어, 다음 그림에서 왼쪽의 경우 $A$공간과 $B$공간은 연결되어 있지 않다고 볼 수 있으며, 오른쪽의 경우 $A$공간과 $B$공간이 연결되었다고 볼 수 있다.

또한, 싸움이 나는 것을 방지하기 위해 정확히 제출한 크기만큼의 공간만 제공되어야 한다.

공학관의 크기와 컴퓨터과학과, 공과대학 측이 제출한 공간의 크기가 주어졌을 때, 어떤 식으로 공간을 나눠야 할지 구해보자.

입력

첫 줄에는 $N$ 이 주어진다. $(1 \le N \le 100)$ 

두 번째 줄에는 컴퓨터과학과가 필요한 공간의 크기 $C$, 다른 공과대학 학과들이 필요한 공간의 크기 $E$가 주어진다. $(1 \le C, E \le N ^ 2)$ 

출력

주어진 조건을 맞춰 공간을 나눌 수 없다면 -1을 출력한다.

주어진 조건을 맞춰 공간을 분할할 수 있다면, 첫 줄에 1을 출력한다. 또한, 두 번째 줄부터 $N$줄에 걸쳐 공간을 나눈 결과를 출력한다. 여기서 1은 컴퓨터과학과의 공간, 2는 공과대학의 공간이며, 0은 바리케이드다.

풀이

공간을 분리하는 여러 문제를 접했었는데,
이번문제를 보며 확실해진건,
공간을 딱 2군데로 분할할때 가장 적합한방법은 대각선으로 분할하는것이다.

A공간. 즉 컴퓨터과학과 공간을 위그림순서대로 먼저채우고, 남은공간에 한칸띄어서 공과대학생을 넣으면 되는문제다.

컴퓨터과학과(A)를 배치하는 코드이다.
cnt_a의 값은

보라색으로 표시한곳까지의 A를 배치할수있는 수이다.
한마디로 저 위치까지는 cnt_a > 0 의코드를통해 배치를하고
cnt_a == 0 인, 13번째칸에는 한번만,
그 이후부터는 초록색 화살표를 따라 A를 배치하는 코드이다.

A를 배치한뒤에는 B를 배치할건데,
모든 좌표를 탐색, A가 배치되지않은 빈공간이면,

이 방향벡터를 그 위치기준으로 + 하여, 오른쪽 아래 왼쪽 위에
A가없으면 그 위치에 B를 배치하였다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
//n, c, e : 입력값
//cnt: 공과대학생수를셀것
//map: 학생들의 배치도
int n, c, e, cnt, ** map; 
int dx[4] = { 0, 1, 0, -1 }; //우 하 좌 상 순서
int dy[4] = { 1, 0, -1, 0 };

int main(void) {
	scanf("%d%d%d", &n, &c, &e);
	cnt = e; 
	if (c > n * n) { //컴퓨터공학과 학생수가 맵보다크면
		printf("-1");
		return 0;
	}
	map = new int* [n];
	//맵 생성, 초기화
	for (int i = 0; i < n; i++) {
		map[i] = new int[n];
		for (int j = 0; j < n; j++)
			map[i][j] = 0; //빈공간 즉 바리게이트
	}

	//컴퓨터과학과 학생(A)을 배치
	int x = 0, y = 0, gap1 = 1, gap2 = 1, cnt_a = 0;
	for (int k = 1; k <= n; k++) cnt_a += k;
	while (c--) {
		map[x][y] = 1; //현재위치에 A그룹을 설치
		cnt_a--;
		if (cnt_a > 0) {
			x -= 1; y += 1; //우상단방향으로 설치
			if (x < 0) {
				x = gap1; y = 0;
				gap1++;
			}
		}
		else if (cnt_a == 0) {
			x = 1; y = n - 1;
		}
		else {
			x += 1; y -= 1; //좌상단으로설치
			if (y < gap2) {
				gap2++;
				x = gap2;  y = n - 1;
			}
		}
		
	}

	int res = 0;

	//공과대학생(B )을 배치
	for (int i = 0; i < n; i++) {
		if (cnt == 0) break;
		for (int j = 0; j < n; j++) { //현재위치 i,j 탐색
			if (cnt == 0) break;
			if (map[i][j] == 1) continue; //이미 컴퓨터과학과공간이면 제외
			bool isBlank = true; //빈공간인가? => 공과대학생공간 설치가 가능한가?
			for (int k = 0; k < 4; k++) { //현재위치 i,j에서 상하좌우를 탐색
				int xx = i + dx[k];
				int yy = j + dy[k];
				if (xx < 0 || y < 0 || n == xx || n == yy) continue; //맵크기를 벗어나면 제외
				if (map[xx][yy] == 1) { //i,j 기준 상하좌우에 컴퓨터과학과공간이 설치되있으면
					isBlank = false; //빈공간이 아님
					break; //상하좌우 탐색종료
				}
			}
			if (isBlank) {
				map[i][j] = 2; //현재위치를 공과대학생공간으로 기록
				res++;
				cnt--; //공과대학생수 카운트
			}
		}
	}

	if (res < e)
		printf("-1");
	else {
		printf("1\n");
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				printf("%d", map[i][j]);
			}
			printf("\n");
		}
	}

	return 0;
}