개발 블로그

문제 링크 : 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/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;
}

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

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.

낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.

1. 낚시왕이 오른쪽으로 한 칸 이동한다.
2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
3. 상어가 이동한다.

상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.

왼쪽 그림의 상태에서 1초가 지나면 오른쪽 상태가 된다. 상어가 보고 있는 방향이 속도의 방향, 왼쪽 아래에 적힌 정수는 속력이다. 왼쪽 위에 상어를 구분하기 위해 문자를 적었다.

상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.

입력

첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)

둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.

두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

출력

낚시왕이 잡은 상어 크기의 합을 출력한다

각 칸의 왼쪽 아래에 적힌 수는 속력, 오른쪽 아래는 크기, 왼쪽 위는 상어를 구분하기 위한 문자이다. 오른쪽 위에 ❤️는 낚시왕이 잡은 물고기 표시이다.

<예제 입력>

4 6 8

4 1 3 3 8

1 3 5 2 9

2 4 8 4 1

4 5 0 1 4

3 3 1 2 7

1 5 8 4 3

3 6 2 1 2

2 2 2 3 5

<예제 출력>

22

초기 상태

1초

2초 (E번 상어는 B번에게 먹혔다)

3초

4초

5초

6초

접근 방법

이차원 배열 map[][]에 Shark 객체를 담은 벡터를 저장해서 상어 정보를 관리해주었다.

상어를 움질일 때 주의할 점은 두가지인데,

1) 시간 초과를 해결하기 위해 MOD 연산을 이용해서 상어의 속도를 나눠줘야한나는 것과

2) 이동 완료가 된 상어를 임시 벡터에 담았다가 한번에 갱신해야 한다는 점이다. (상어를 하나씩 옮기면 이동 완료가 된 상어를 또 옮기는 경우 발생)

1)에서, modulus를 어떤 수로 잡아야 할까 생각해보자. 

이동을 했는데도 불구하고 이동 전과 변화가 없으면 그때까지의 이동은 할 필요가 없다는 것을 알면된다.

예를 들어 설명해보면,

만약 [3][2]에 d=3인 상어가 있다고 해 보자. 이 상어 속력이 만약 10이면 이동한뒤에도 여전히 처음과 방향과 위치가 같은 상태가 된다. 즉 가로 방향일 때는 modulus = (C-1)*2 로 잡으면 된다. 세로 방향일 때는 (R-1)*2로 잡으면 된다.

(@@@@@@@@@@@@@@@@@

만약 [2][1]에 d=3, s=10이면? -> 10%10 = 0이므로 이동하지 않아도 되는것? -> 실제로 10번 이동하면 d=4로 바뀌는 것을 확인할 수 있음.... 그런데 이 부분 고려하지 않아도 통과는 된다.... 

@@@@@@@@@@@@@@@@@)

#include <iostream>
#include <vector>
using namespace std;

class Shark {

public:
	int r, c, s, d, z;
	Shark(int _r, int _c, int _s, int _d, int _z) {
		r = _r;
		c = _c;
		s = _s;
		d = _d;
		z = _z;

	}
};

int R, C, M;

vector<Shark> map[101][101];
vector<Shark> sharkVec;
//x, 위, 아, 오, 왼
int dr[5] = { 0,-1,1,0,0 };
int dc[5] = { 0,0,0,1,-1 };


int getBottomShark(int col) {
	for (int r = 1; r <= R; r++) {
		if (map[r][col].size() != 0) {
			return r;
		}
	}
	return -1;	//그 줄에 상어 없는 경우 -1 리턴
}

void moveShark() {
	vector<Shark> tmpVec;

	//배열 돌면서 상어 있으면 이동시킴
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			for (int k = 0; k < map[i][j].size(); k++) {//1마리

				int nowDirection = map[i][j][k].d;
				int r = i;
				int c = j;
				int nr, nc;
				int move;

				//시간 초과 해결 부분 ~
				if (nowDirection == 1 || nowDirection == 2) {
					move = map[i][j][k].s % ((R - 1) * 2);				//R-1 * 2 번 움직이면 방향 그대로인 채로 처음 자리로 돌아옴
				}
				else {
					move = map[i][j][k].s % ((C - 1) * 2);				
				}
				//~ 시간 초과 해결 부분 


				for (int p = 0; p < move; p++) {	//속력(이동해야하는 칸 수)번 이동
					nr = r + dr[nowDirection];
					nc = c + dc[nowDirection];

					if (nr<1 || nr>R) {		//범위 넘어가면 방향 젼환

						if (nowDirection == 1) {
							nowDirection = 2;
							nr = r + dr[nowDirection];
							nc = c + dc[nowDirection];
						}
						else if (nowDirection == 2) {
							nowDirection = 1;
							nr = r + dr[nowDirection];
							nc = c + dc[nowDirection];
						}

					}
					if (nc<1 || nc>C) {
						if (nowDirection == 3) {
							nowDirection = 4;
							nr = r + dr[nowDirection];
							nc = c + dc[nowDirection];
						}
						else if (nowDirection == 4) {
							nowDirection = 3;
							nr = r + dr[nowDirection];
							nc = c + dc[nowDirection];
						}
					}
					r = nr; c = nc; //갱신

				}
				//옮길 위치 찾고나서 임시 벡터에 넣고, 옮기기 전의 상어 정보 삭제
				tmpVec.push_back(Shark(r, c, map[i][j][k].s, nowDirection, map[i][j][k].z));
				map[i][j].clear();

			}
		}
	}
	for (int i = 0; i < tmpVec.size(); i++) {
		Shark shark = tmpVec[i];
		int r = shark.r;
		int c = shark.c;
		map[r][c].push_back(shark);
	}
}
void eatShark() {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {

			if (map[i][j].size() >= 2) {		//한 칸에 두마리 이상 있으면 
				int maxSize = 0;
				int maxIdx = 0;

				for (int k = 0; k < map[i][j].size(); k++) {	//가장 큰 상어 찾아서
					if (maxSize < map[i][j][k].z) {
						maxSize = map[i][j][k].z;
						maxIdx = k;
					}
				}
				Shark shark = map[i][j][maxIdx];	//그 상어만 빼고 삭제
				map[i][j].clear();
				map[i][j].push_back(shark);
			}

		}
	}
}


int main() {
	int ans = 0;

	cin >> R >> C >> M;
	if (M == 0) {
		cout << 0;
	}
	else {
		//상어 정보 입력 받기
		for (int t = 0; t < M; t++) {
			int r, c, s, d, z;
			cin >> r >> c >> s >> d >> z;
			Shark shark = Shark(r, c, s, d, z);
			map[r][c].push_back(shark);
			sharkVec.push_back(shark);
		}


		//낚시왕 1~C 까지 이동
		for (int i = 1; i <= C; i++) {
			int sharkRow = getBottomShark(i);
			if (sharkRow != -1) {					//낚시왕 아래에 상어 있으면 

				//가장 아래 있는 상어 낚시
				ans += map[sharkRow][i][0].z;

				map[sharkRow][i].clear();


			}
			//상어 이동
			moveShark();

			//제일 큰 상어 1마리만 남기고 잡아먹기
			eatShark();

		}


		cout << ans;
	}


	return 0;
}