개발 블로그

문제 링크 : www.acmicpc.net/problem/19237

문제

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.

N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.

각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.

모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.

<그림 1>은 맨 처음에 모든 상어가 자신의 냄새를 뿌린 상태를 나타내며, <표 1>에는 각 상어 및 현재 방향에 따른 우선순위가 표시되어 있다. 이 예제에서는 k = 4이다. 왼쪽 하단에 적힌 정수는 냄새를 의미하고, 그 값은 사라지기까지 남은 시간이다. 좌측 상단에 적힌 정수는 상어의 번호 또는 냄새를 뿌린 상어의 번호를 의미한다.

<그림 2>

<그림 3>

<그림 2>는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태이고, <그림 3>은 <그림 2>의 상태에서 한 칸 더 이동한 것이다. (2, 4)에는 상어 2과 4가 같이 도달했기 때문에, 상어 4는 격자 밖으로 쫓겨났다.

<그림 4>

<그림 5>

<그림 4>은 격자에 남아있는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태, <그림 5>는 <그림 4>에서 한 칸 더 이동한 상태를 나타낸다. 상어 2는 인접한 칸 중에 아무 냄새도 없는 칸이 없으므로 자신의 냄새가 들어있는 (2, 4)으로 이동했다. 상어가 이동한 후에, 맨 처음에 각 상어가 뿌린 냄새는 사라졌다.

이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.

입력

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)

그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.

그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.

그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다. 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다. 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.

맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.

출력

1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.

접근 방법

1단계 : 4방향 검사

현재 상어를 방향을 기준으로 우선위에 따라 돌아가면서 다음 칸을 검사한다.

돌면서 내 냄새와 같은 칸이 나오면 그 값을 저장한다. 그리고 계속 검사한다. 왜냐하면 빈칸이고 냄새가 없는 칸이 나올수도 있기 때문이다. 후자의 경우가 더 우선순위가 높으므로 검사를 멈추면 안된다. (4방향 중  또 내 냄새와 같은 칸이 나오면 그 값은 그냥 건너 뛴다. 이미 우선순위에 의해 이동할 위치가 정해졌으므로)

돌면서 빈칸이고 냄새가 없는 칸이 나오면 현재 칸은 상어가 없는것으로 표시하고 이 경우가 가장 우선순위가 높으므로 다른 방향을 조사할 필요 없이 검사를 중단한다.

2단계 

CASE 1 

위에서 상어가 없고, 냄새도 없는 칸을 찾은 경우에는 해당 상어의 위치 정보를 바꿔주고(이차 배열은 아직 안바꿈), 임시 벡터를 만들어서 해당 칸에 상어 번호를 넣는다. (나중에 가장 작은 상어만 남겨놓고 다 내보내기 위함)

CASE 2

CASE1 에 해당하지 못할 경우에는 내냄새와 같은 칸으로 이동해야 한다. 1단계에서 값을 저장해놓았으므로 상어 객체 정보를 갱신한다.

CASE 3

이외 상황은 문제에서 조건으로 주어지지 않았으므로 고려하지 않아도 된다.

3단계

M개의 상어에 대해 어디 위치로 이동해야할지 조사가 다 끝났으니 정보를 갱신해야한다.

아까 위의 2단계-CASE1 에서 가장 번호가 작은 상어만 남겨놓고 나머지는 내보내는 것을 안 했으니 3단계에서 수행해준다. 임시 3차원 벡터 tmp를 돌면서 그 칸의 후보가 1이면 그냥 넣어주고, 2이상이면 상어 번호들을 비교해서 가장 최소 번호 상어만 남기고 다 지운다. (goOut()에서 수행한다.)

또한 내보낸 상어들 수를 카운트해서 처음 상어에서 빼준다. 

4단계

이제 냄새를 1씩 감소해준다. 이때 주의할 점은 상어가 있는 칸을 제외하고 1을 감소시켜줘야 한다.

위 단계들을 반복하면서 남은 상어가 1마리인데 그 상어 번호가 1일 때까지 반복하며, 1000번 넘게 반복하면 스탑한다.

#include <iostream>
#include <vector>
#include <utility>

using namespace std;


class Shark {
public:
	int r, c, d;
	int dirArr[5][5];
	bool live;
	Shark() {}
	Shark(int _r, int _c, int _d, int _dirArr[5][5], bool _live) {
		r = _r;
		c = _c;
		d = _d;
		for (int i = 1; i <=4; i++) {
			for (int j = 1; j<=4; j++) {
				dirArr[i][j] = _dirArr[i][j];
			}
		}
		live = _live;
	}
};
pair<int, pair<int, int>> sharkMap[21][21];	//현재 상어 번호
Shark sharkArr[400];
int N, M, k;

//x, 위 아 왼 오
int dr[5] = { 0,-1,1,0,0 };
int dc[5] = { 0,0,0,-1,1 };


//1초 지나서 k감소
void decreaseK() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (sharkMap[i][j].first==-1 && sharkMap[i][j].second.second > 0) {		//상어가 떠난 자리에 냄새가 남아있는 칸이면
				sharkMap[i][j].second.second -= 1;
			}
		}
	}

}
void goOut(vector<int> vec, int left, int nr, int nc) {		//vec 중에서 left 빼고 다 내보내기
	//sharkArr 처리
	for (int i = 0; i < vec.size(); i++) {
		if (vec[i] != left) {	//나머지들 내보내기
			sharkArr[vec[i]].live = false;
		}
	}
	//sharkMap 처리
	sharkMap[nr][nc] = make_pair(left, make_pair(left, k));
}



int main() {

	cin >> N >> M >> k;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int sharkNum; cin >> sharkNum;
			if (sharkNum != 0) {
				sharkMap[i][j] = make_pair(sharkNum, make_pair(sharkNum, k));
				sharkArr[sharkNum].r = i;
				sharkArr[sharkNum].c = j;
				sharkArr[sharkNum].live = true;
			}
			else {
				sharkMap[i][j] = make_pair(-1, make_pair(-1, 0));
			}
		}
	}
	
	//상어 m 마리의 방향
	for (int i = 1; i <= M; i++) {
		int dir; cin >> dir;
		sharkArr[i].d = dir;
	}

	//상어 m 마리의 우선순위
	for (int m = 1; m <= M; m++) {

		for (int i = 1; i <= 4; i++) {
			for (int j = 1; j <= 4; j++) {
				cin >> sharkArr[m].dirArr[i][j];
			}
		}
	}



	int leftSharkCnt = M;		//격자 안에 남아있는 상어 수 
	int sec = 0;

	while (sec <= 1000) {

		if (leftSharkCnt == 1 && sharkArr[1].live == true) break;


		vector<int> tmp[21][21];	//움직이고나서의 상어 번호 저장 
		//상어 1번부터 M번까지 동시에 이동
		for (int s = 1; s <= M; s++) {
			if (sharkArr[s].live == false) continue;	//이미 나간 상어

			pair<int, int> sameSmellLoc = make_pair(-1, -1);
			int toSameSmellmoveDir = 0;
			int curR = sharkArr[s].r;
			int curC = sharkArr[s].c;
			int curD = sharkArr[s].d;


			//아무것도 없는 빈 칸(k<=0) -> 자신의 냄새 있는 칸 
			bool isEmpty = false;
			int nr, nc, nd;

			//1단계
			for (int i = 1; i <= 4; i++) {
				nd = sharkArr[s].dirArr[curD][i];		
				nr = curR + dr[nd];
				nc = curC + dc[nd];
				if (nr <= 0 || nr > N || nc <= 0 || nc > N) continue;

				if (sharkMap[nr][nc].first == -1 && sharkMap[nr][nc].second.second<=0) {		//빈칸이고 냄새 없음 
					
					isEmpty = true; 
					sharkMap[curR][curC].first = -1;									//현재칸 상어 없애기
					break;
				}
				else if (sharkMap[nr][nc].second.second >= 0 && sharkMap[nr][nc].second.first == s) {
					if (sameSmellLoc.first == -1) {	//내냄새와 같은 첫 위치만 저장
						sameSmellLoc.first = nr;
						sameSmellLoc.second = nc;
						toSameSmellmoveDir = nd;
					}
				}

			}

			//2단계
			if (isEmpty == false) {
				//위에서 저장한 내 냄새가 있는 칸으로 이동 
				sharkMap[sameSmellLoc.first][sameSmellLoc.second] = make_pair(s, make_pair(s, k));
				sharkArr[s].r = sameSmellLoc.first;
				sharkArr[s].c = sameSmellLoc.second;
				sharkArr[s].d = toSameSmellmoveDir;

				
				sharkMap[curR][curC].first = -1;					//이동 후 현재 위치 있던거 삭제
			}

			else {
				sharkArr[s].r = nr;		sharkArr[s].c = nc;		sharkArr[s].d = nd;
				tmp[nr][nc].push_back(s);			//일단 후보들 킵
			}
		}


		//3단계 
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (tmp[i][j].size() == 0) continue;
				else if (tmp[i][j].size() == 1) {
					int shark_num = tmp[i][j][0];
					sharkMap[i][j] = make_pair(shark_num, make_pair(shark_num, k));
				}
				else {	//2개 이상
					int mini = 1000;
					for (int k = 0; k < tmp[i][j].size(); k++) {
						if (mini > tmp[i][j][k]) mini = tmp[i][j][k];
					}
					goOut(tmp[i][j], mini, i, j);	//(i,j)에 mini번 상어만 남기기
					leftSharkCnt = leftSharkCnt - tmp[i][j].size() + 1;	//한개만 빼고 다 내보냄

				}
			}
		}

		//4단계
		//상어 이동 완료 후 
		decreaseK();


		//모든 상어 동시에 이동 후 sec 증가
		sec++;


	}

	if (sec > 1000) cout << -1;
	else cout << sec;


	return 0;
}

문제 링크 : www.acmicpc.net/problem/17779

문제

재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

선거구를 나누는 방법은 다음과 같다.

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
2. 다음 칸은 경계선이다.
   1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
   2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
   3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
   4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.
   • 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
   • 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
   • 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
   • 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

아래는 크기가 7×7인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.

구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

입력

첫째 줄에 재현시의 크기 N이 주어진다.

둘째 줄부터 N개의 줄에 N개의 정수가 주어진다. r행 c열의 정수는 A[r][c]를 의미한다.

출력

첫째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력한다.

제한

• 5 ≤ N ≤ 20
• 1 ≤ A[r][c] ≤ 100

접근 방법

4중 포문을 돌면서 (x,y,d1,d2) 조합을 정한다. (범위 넘어가면 continue 로 넘어간다.)

그렇게 정한 (x,y,d1,d2) 쌍에 대해 아래 순서로 5 선거구역을 표시한다.

1단계 : 5선거구역 표시 => bool divide();

1) (x, y)에서 시작해서 왼쪽 아래 대각선으로 d1만큼 한 번 씩 내려간다. (< v)

2) 한 줄 씩 내려가면서 가로로 y까지 5 선거구역임을 표시한다.

3 )(x, y)에서 시작해서 오른쪽 아래 대각선으로 d2만큼 한 번 씩 내려간다.(> v)

4) 한 줄 씩 내려가면서 y부터 가로로 y까지 5 선거구역임을 표시한다.

5) 위의 1),2)번을 수행한 뒤의 위치부터 다시 오른쪽 대각선 아래로 d2만큼 한 번 씩 이동한다. (> v)

6) 한 줄 씩 내려가면서 가로로 y까지 5 선거구역임을 표시한다.

7) 위의 3),4)번을 수행한 뒤의 위치부터 다시 왼쪽 대각선 아래로 d1만큼 한 번 씩 이동한다. (< v)

8) ) 한 줄 씩 내려가면서 y부터 가로로 y까지 5 선거구역임을 표시한다.

이렇게 하면 5선거구역 표시가 끝난다.

2단계 : 1~4 선거구역 표시 => getpartOne(); getpartTwo(); getpartThree(); getpartFour();

그 다음은 문제에서 주어진 아래의 1~4 선거구역의 범위에 따라

• 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
• 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
• 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
• 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

이미 5선거구역으로 표시되어 있는 곳을 제외하고 해당 선거구역 숫자료 표시해 주면 된다.

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;


int A[21][21];
//위 오 아 왼
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };

int divideMap[21][21];
int N;


//1~N 사이에 들어오는지 범위 체크
bool chk(int r, int c) {
	if (r<1 || r>N || c<1 || c>N) return false;
	return true;
}

//1~4 선거구역 표시. 5가 이미 표시되어 있는 경우 패스
int  getpartOne(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = 1; i < x + d1; i++) {
		for (int j = 1; j <= y; j++) {
			if (divideMap[i][j] != 5) {		//5구역 만나면 다음 줄
				divideMap[i][j] = 1;
				sum += A[i][j];
			}
		}
	}
	return sum;
}
int getpartTwo(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = 1; i <= x + d2; i++) {		//1~4
		for (int j = y + 1; j <= N; j++) {	//6~7
			if (divideMap[i][j] != 5) {
				divideMap[i][j] = 2;
				sum += A[i][j];
			}
		}
	}
	return sum;
}
int getpartThree(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = x + d1; i <= N; i++) {		//i = 5,6,7
		for (int j = 1; j < y - d1 + d2; j++) {
			if (divideMap[i][j] != 5) {
				divideMap[i][j] = 3;
				sum += A[i][j];
			}

		}
	}return sum;
}
int getpartFour(int x, int y, int d1, int d2) {
	int sum = 0;

	for (int i = x + d2 + 1; i <= N; i++) {
		for (int j = y - d1 + d2; j <= N; j++) {		
			if (divideMap[i][j] != 5) {
				divideMap[i][j] = 4;
				sum += A[i][j];
			}
		}
	}return sum;
}

//5선거구역 표시. 범위 넘어가서 다른 선거구역의 크기가 최소 1이상 되지 않는 경우 false 리턴
bool divide(int x, int y, int d1, int d2) {		
	memset(divideMap, 0, sizeof(divideMap));

	divideMap[x][y] = 5;
	int initR = x;
	int initC = y;

	//1
	for (int k = 0; k < d1; k++) {
		int nr = initR + 1;
		int nc = initC - 1;
		if (!chk(nr, nc)) {
			return false;
		}
		initR = nr;
		initC = nc;
		for (int col = nc; col <= y; col++) {
			divideMap[nr][col] = 5;
		}

	}
	//2
	int initR2 = x;
	int initC2 = y;
	for (int k = 0; k < d2; k++) {
		int nr = initR2 + 1;
		int nc = initC2 + 1;
		if (!chk(nr, nc)) {
			return false;
		}
		initR2 = nr;
		initC2 = nc;
		for (int col = y; col <= nc; col++) {
			divideMap[nr][col] = 5;
		}

	}

	//3
	int startR = x + d1;
	int startC = y - d1;
	for (int k = 0; k < d2; k++) {
		int nr = startR + 1;
		int nc = startC + 1;
		if (!chk(nr, nc)) {
			return false;
		}
		startR = nr;
		startC = nc;
		for (int col = nc; col <= y - d1 + d2; col++) {
			divideMap[nr][col] = 5;
		}

	}


	int startR2 = x + d2;
	int startC2 = y + d2;
	for (int k = 0; k < d1; k++) {
		int nr = startR2 + 1;
		int nc = startC2 - 1;
		if (!chk(nr, nc)) {
			return false;
		}
		startR2 = nr;
		startC2 = nc;
		for (int col = y - d1 + d2; col <= nc; col++) {
			divideMap[nr][col] = 5;
		}

	}

	return true;

}



int main() {

	cin >> N;
	int sumA = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> A[i][j];
			sumA += A[i][j];
		}
	}

	//각 칸을 돌면서 기준점 정함

	int mini = 987654321;
	for (int x = 1; x <= N; x++) {		//행
		for (int y = 1; y <= N; y++) {		//열

			for (int d1 = 1; d1 <= 18; d1++) {
				for (int d2 = 1; d2 <= 18; d2++) {
					if (x + d1 + d2 > N) break;


					if (!divide(x, y, d1, d2)) continue;

					int sum1 = getpartOne(x, y, d1, d2);
					int sum2 = getpartTwo(x, y, d1, d2);
					int sum3 = getpartThree(x, y, d1, d2);
					int sum4 = getpartFour(x, y, d1, d2);
					int sum5 = sumA - (sum1 + sum2 + sum3 + sum4);

					//각 선거구역 크기는 최소 1칸 이상
					if (sum1 >= 1 && sum2 >= 1 && sum3 >= 1 && sum4 >= 1 && sum5 >= 1) {// 선거구는 구역을 적어도 하나 포함해야 하고
						vector<int> vec = { sum1, sum2, sum3, sum4, sum5 };
						sort(vec.begin(), vec.end());

						int maxNum = vec[4];
						int minNum = vec[0];
						if (mini > maxNum - minNum) mini = maxNum - minNum;
					}

				}
			}
		}
	}

	cout << mini;



	return 0;
}

문제 링크 : www.acmicpc.net/problem/17142

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.

2 0 0 0 1 1 0

0 0 1 0 1 2 0

0 1 1 0 1 0 0

0 1 0 0 0 0 0

0 0 0 2 0 1 1

0 1 0 0 0 0 0

2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

* 6 5 4 - - 2

5 6 - 3 - 0 1

4 - - 2 - 1 2

3 - 2 1 2 2 3

2 2 1 0 1 - -

1 - 2 1 2 3 4

0 - 3 2 3 4 *

시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2

1 2 - 3 - 0 1

2 - - 2 - 1 2

3 - 2 1 2 2 3

3 2 1 0 1 - -

4 - 2 1 2 3 4

* - 3 2 3 4 *

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

입력

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

접근 방법

전체 바이러스 중에 DFS를 활용한 중복조합을 이용해서 M개를 픽해준다. (활성 상태로 만들 바이러스 선택)

활성상태로 만들 바이러스를 queue에 넣고 BFS를 돌면서 fromStart배열 요소를 하나씩 증가해 나간다.

여기서 주의해야할 경우는 다음에 방문할 칸인 fromStart[nr][nc]가 빈칸이 아닌 비활성 상태의 바이러스인 경우이다. 

* 비활성 바이러스를 활성 바이러스 상태로 바꾸는데에는 1초가 소요되지 않는다. (문제 조건에는 빈칸->바이러스 상태가 되는 경우에 1초가 소요된다고만 나와있기 때문)

그리고 fromStart[nr][nc]들의 값을 비교해서 가장 큰 값을 ansVec에 push 해야하는데 (넣어놓고 마지막에 모든 빈칸에 바이러스가 퍼지기까지 걸리는 최소시간 구하기 위함) 그 fomStart[nr][nc]의 값을 최대인지 비교하는 조건문은 다음에 방문할 칸이 빈 칸인 경우에만 실행되도록 한다. (

이러한 로직으로 풀면 답이 통과된다. 

#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;

int map[50][50];
vector<pair<int, int>> initVirus;	//처음 2(바이러스) 위치
int visited[10] = { 0 };			//처음 2(바이스) 활성 선택 여부
vector<int> virusIdx;				//전체 바이러스 중 M개를 담는 벡터
//위 오 아 왼
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
int N, M;
int space = 0;	//빈칸
vector<int> ansVec;
void spreadBFS() {

	int maxSecond = 0;
	int fromStart[50][50];
	int initLoc[50][50];
	memset(fromStart, 0, sizeof(fromStart));
	memset(initLoc, 0, sizeof(initLoc));
	queue<pair<int, int>> que;
	int cnt = 0;

	for (int i = 0; i < virusIdx.size(); i++) {	//M개
		que.push(initVirus[virusIdx[i]]);
		initLoc[initVirus[virusIdx[i]].first][initVirus[virusIdx[i]].second] = 1;		//처음 바이러스가 있던 시작점
	}
	while (!que.empty()) {
		int r = que.front().first;
		int c = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (nr < 0 || nr >= N || nc < 0 || nc >= N ||		//범위 벗어나거나
				map[nr][nc] == 1 || fromStart[nr][nc] != 0 || initLoc[nr][nc] == 1) continue;	//벽이거나, 이미 바이러스 퍼졌거나, 처음 활성바이러스 위치면 스킵

			//빈칸이던 비활성바이러스이던 둘 다
			fromStart[nr][nc] = fromStart[r][c] + 1;
			que.push(make_pair(nr, nc));

			//비활성 바이러스 아니고 빈칸인 경우에
			if (map[nr][nc] == 0) {
				cnt++;		//빈칸에서 바이러스 상태 된 칸의 수 카운트
				if (maxSecond < fromStart[nr][nc]) maxSecond = fromStart[nr][nc];	//이 경우에만 최대로 걸린 초 고려하기
			}

		}

	}

	if (cnt == space) {			//모든 빈칸에 다 퍼졌으면 
		ansVec.push_back(maxSecond);
	}
}


void pickDFS(int toPick, int start) {			//전체 바이러스 중 M개 픽

	if (toPick == 0) {
		spreadBFS();
	}

	for (int i = start; i < initVirus.size(); i++) {
		if (visited[i] == 0) {
			visited[i] = 1;
			virusIdx.push_back(i);
			pickDFS(toPick - 1, i);
			virusIdx.pop_back();
			visited[i] = 0;
		}
	}
}


int main() {

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				initVirus.push_back(make_pair(i, j));
			}
			else if (map[i][j] == 0) space++;
		}
	}


	//initVec에서 활성상태로 만들 바이러스 M개 고르기
	pickDFS(M, 0);

	if (ansVec.size() == 0) cout << -1;
	else {
		sort(ansVec.begin(), ansVec.end());
		cout << ansVec[0];
	}
	return 0;
}

문제 링크 : www.acmicpc.net/problem/20061

문제

모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다.

<그림 1> 모노미노도미노 게임 보드

이 게임에서 사용하는 블록은 타일 하나 또는 두 개가 가로 또는 세로로 붙어있는 형태이다. 아래와 같이 세 종류가 있으며, 왼쪽부터 순서대로 크기가 1×1, 1×2, 2×1 이다.

<그림 2> 모노미노도미노 게임에서 사용하는 블록

블록을 놓을 위치를 빨간색 보드에서 선택하면, 그 위치부터 초록색 보드로 블록이 이동하고, 파란색 보드로 블록이 이동한다. 블록의 이동은 다른 블록을 만나거나 보드의 경계를 만나기 전까지 계속해서 이동한다. 예를 들어, 크기가 1×1인 블록을 (1, 1)에 놓으면, 보드의 상태는 <그림 3>과 같이 변한다.

<그림 3>

여기서 크기가 1×2인 블록을 (3, 0)과 (3, 1)에 놓으면 <그림 4>와 같이 보드의 상태가 변한다.

<그림 4>

다시 이 상태에서 크기가 2×1인 블록을 (2, 2), (3, 2)와 (2, 3), (3, 3)에 놓으면 <그림 5>와 같이 변한다.

<그림 5>

초록색 보드의 4번 행은 모든 칸이 타일로 가득 차있다. 이렇게 초록색 보드에서 어떤 행이 타일로 가득 차 있다면, 그 행의 타일은 모두 사라진다. 사라진 이후에는 초록색 보드에서 사라진 행의 위에 있는 블록이 사라진 행의 수만큼 아래로 이동한다. 파란색의 경우는 열이 타일로 가득 차 있으면, 그 열의 타일이 모두 사라지며, 사라진 이후에는 파란색 보드에서 사라진 열의 왼쪽에 있는 블록이 사라진 열의 수만큼 오른쪽으로 이동한다. 이렇게 한 행이나 열이 타일로 가득 차서 사라지면 1점을 획득한다. 점수는 사라진 행 또는 열의 수와 같다. 만약, 두 개의 행이 사라지면 2점을 획득하게 되고, 한 행과 한 열이 사라져도 2점을 획득하게 된다. 위의 보드는 아래와 같이 변하고, 1점을 얻는다.

<그림 6>

여기서 크기가 2×1인 블록을 (1, 3), (2, 3)에 놓으면 보드는 <그림 7>과 같이 변한다.

<그림 7>

초록색 보드의 0, 1번 행과 파란색 보드의 0, 1번 열은 그림에는 연한색으로 표현되어 있는 특별한 칸이다. 초록색 보드의 0, 1번 행에 블록이 있으면, 블록이 있는 행의 수만큼 아래 행에 있는 타일이 사라지고, 초록색 보드의 모든 블록이 사라진 행의 수만큼 아래로 이동하고, 파란색 보드의 0, 1번 열에 블록이 있으면, 블록이 있는 열의 수만큼 오른쪽 열에 있는 타일이 사라지고, 파란색 보드의 모든 블록이 사라진 열의 수만큼 이동하게 된다. 위의 그림은 파란색 보드의 1번 열에 블록이 있기 때문에, 5번 열에 있는 블록이 모두 사라지고, 파란색 보드의 모든 블록이 오른쪽으로 한 칸 이동하게 된다. 따라서, 보드는 <그림 8>과 같이 변하게 된다.

<그림 8>

위의 보드에서 1×2인 블록을 (0, 0), (0, 1)에 놓으면 <그림 9>와 같다.

<그림 9>

여기서 크기가 2×1인 블록을 (2, 0), (3, 0)에 놓으면 <그림 10>과 같이 변한다. 파란색 보드는 1번 열에 블록이 생겨서 오른쪽으로 한 칸씩 이동한 상태이다.

<그림 10>

크기가 2×1인 블록을 (1, 2), (2, 2)에 놓으면, <그림 11>과 같이 변한다.

<그림 11>

파란색 보드는 1번 열에 블록이 있기 때문에, 5번 열의 타일이 사라지고 모든 블록이 오른쪽으로 한 칸씩 이동하게 된다. 초록색 보드는 4번 행의 모든 칸에 타일이 있기 때문에, 1점을 얻으면서, 4번 행의 모든 타일이 사라진다.

<그림 12>

<그림 12>는 <그림 11>의 상태에서 파란색 보드는 모든 블록이 오른쪽으로 한 칸 이동했고, 초록색 보드의 4번 행이 모두 사라진 상태이다. 이제, 초록색 보드에서 사라진 행의 위에 있는 블록이 아래로 한 칸씩 내려와야 한다. 이동한 후의 상태는 <그림 13>과 같다.

<그림 13>

행이나 열이 타일로 가득찬 경우와 연한 칸에 블록이 있는 경우가 동시에 발생할 수 있다. 이 경우에는 행이나 열이 타일로 가득 찬 경우가 없을 때까지 점수를 획득하는 과정이 모두 진행된 후, 연한 칸에 블록이 있는 경우를 처리해야 한다.

블록은 보드에 놓인 이후에 다른 블록과 합쳐지지 않는다. 블록을 놓은 위치가 순서대로 주어졌을 때, 얻은 점수와 초록색 보드와 파란색 보드에 타일이 있는 칸의 개수를 모두 구해보자.

입력

첫째 줄에 블록을 놓은 횟수 N(1 ≤ N ≤ 10,000)이 주어진다.

둘째 줄부터 N개의 줄에 블록을 놓은 정보가 한 줄에 하나씩 순서대로 주어지며, t x y와 같은 형태이다.

• t = 1: 크기가 1×1인 블록을 (x, y)에 놓은 경우
• t = 2: 크기가 1×2인 블록을 (x, y), (x, y+1)에 놓은 경우
• t = 3: 크기가 2×1인 블록을 (x, y), (x+1, y)에 놓은 경우

블록이 차지하는 칸이 빨간색 칸의 경계를 넘어가는 경우는 입력으로 주어지지 않는다.

출력

첫째 줄에 블록을 모두 놓았을 때 얻은 점수를 출력한다.

둘째 줄에는 파란색 보드와 초록색 보드에서 타일이 들어있는 칸의 개수를 출력한다.

접근 방법

줄이 꽉 차서 삭제하고 한줄씩 밀 때, 인덱스를 증가시켜서 

밀려서 검사하지 못한 그 줄을 검사해줘야한다.

처음에는 while(1)문 안에서

꽉 찬 줄을 찾고 한 줄씩 삭제했다. 5~0 돌고 삭제하고 다시 5~0을 돌았다. 그랬더니 계속 '틀렸습니다' 가 떴다. 그래서 5~0 번은 한 번만 돌고 꽉 찬 줄을 발견했을 때 인덱스를 조정해서 멈췄던 곳 부터 다시 진행을 했다.

shift 할 때 마지막 줄은 따로 삭제를 해줘야하는 것도 주의하자.

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

int red[4][4];
int blue[4][6];
int green[6][4];
int ans = 0;
//열 지우는 함수
void delColBlue(int col) {
	for (int r = 0; r < 4; r++) {
		blue[r][col] = 0;
	}
}
void delRowGreen(int row) {
	for (int c = 0; c < 4; c++) {
		green[row][c] = 0;
	}
}


int maxBlue(int row) {//걸리지 않을때까지 오른쪽 또는 아래로 밀었을 때 

	for (int col = 0; col <= 5; col++) {
		if (blue[row][col] == 1) {
			return col - 1;
		}
	}return 5;
}
int maxGreen(int col) {
	for (int row = 0; row <= 5; row++) {
		if (green[row][col] == 1) {
			return row - 1;
		}
	}return 5;
}

//STEP 1 : 블록 놓기 
void shiftFunc(int t, int x, int y) {

	if (t == 1) {
		blue[x][maxBlue(x)] = 1;
		green[maxGreen(y)][y] = 1;

	}
	else if (t == 2) {	//1*2
		int c = maxBlue(x);
		blue[x][c] = 1;
		blue[x][c - 1] = 1;

		int r = maxGreen(y);
		int r2 = maxGreen(y + 1);
		if (r < r2) {
			green[r][y] = 1;
			green[r][y + 1] = 1;
		}
		else {
			green[r2][y] = 1;
			green[r2][y + 1] = 1;
		}

	}
	else {	//2*1
		int c = maxBlue(x);
		int c2 = maxBlue(x + 1);
		if (c < c2) {
			blue[x][c] = 1;
			blue[x + 1][c] = 1;
		}
		else {
			blue[x][c2] = 1;
			blue[x + 1][c2] = 1;
		}

		int r = maxGreen(y);
		green[r][y] = 1;
		green[r - 1][y] = 1;
	}
}

void eraseAndpushBlue(int col) {
	for (int c = col; c >= 1; c--) {
		for (int r = 0; r < 4; r++) {
			blue[r][c] = blue[r][c - 1];
		}
	}
}
void eraseAndpushGreen(int row) {
	for (int r = row; r >= 1; r--) {
		for (int c = 0; c < 4; c++) {
			green[r][c] = green[r - 1][c];
		}
	}
}

//STEP 2 : 가장 오른쪽 또는 아래부터 4칸 다 찬 줄을 찾아서 삭제하고 shift
void getFullLine() {
	//blue
	for (int c = 5; c >= 2; c--) {
		int cnt = 0;
		for (int r = 0; r < 4; r++) {
			if (blue[r][c] == 0) break;
			else cnt++;
		}
		if (cnt == 4) {
			ans++;
			eraseAndpushBlue(c);
			c++;
		}
	}
	//green
	for (int r = 5; r >= 2; r--) {
		int cnt = 0;
		for (int c = 0; c < 4; c++) {
			if (green[r][c] == 0) break;
			else cnt++;
		}
		if (cnt == 4) {
			ans++;
			eraseAndpushGreen(r);
			r++;
		}

	}

}

//STEP 3 : 0, 1 번째 줄에 블록 있을 때 있는 줄의 수 만큼 shift
void specialBlue() {
	int cnt = 0;
	for (int c = 0; c <= 1; c++) {
		for (int r = 0; r < 4; r++) {
			if (blue[r][c] == 1) {
				cnt++;
				break;
			}
		}
	}
	for (int c = 5; c >= 2; c--) {
		for (int r = 0; r < 4; r++) {
			blue[r][c] = blue[r][c - cnt];
		}
	}
	delColBlue(1);
	delColBlue(0);
}

void specialGreen() {
	int cnt = 0;
	for (int r = 0; r <= 1; r++) {
		for (int c = 0; c < 4; c++) {
			if (green[r][c] == 1) {
				cnt++;
				break;
			}
		}
	}
	for (int r = 5; r >= 2; r--) {
		for (int c = 0; c < 4; c++) {
			green[r][c] = green[r - cnt][c];
		}
	}
	delRowGreen(0);
	delRowGreen(1);
}


//블록 수 카운트
int tileBlue() {
	int res = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 6; j++) {
			if (blue[i][j] == 1) res++;
		}
	}
	return res;
}
int tileGreen() {
	int res = 0;
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 4; j++) {
			if (green[i][j] == 1) res++;
		}
	}
	return res;
}



int main() {

	int N; cin >> N;

	memset(red, 0, sizeof(red));
	memset(blue, 0, sizeof(blue));
	memset(green, 0, sizeof(green));
	for (int T = 0; T < N; T++) {

		int t, x, y;
		cin >> t >> x >> y;

		shiftFunc(t, x, y);	//빨간색에서 파란색, 초록색 보드로 타일 밀기
		getFullLine();
		specialBlue();
		specialGreen();
	}
	cout << ans << "\n" << tileBlue() + tileGreen();


	return 0;
}