728x90
728x90

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

 

19237번: 어른 상어

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미

www.acmicpc.net

 

문제

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 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;
}
728x90
728x90

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

 

19236번: 청소년 상어

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는

www.acmicpc.net

 

 

 

문제

아기 상어가 성장해 청소년 상어가 되었다.

4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.

오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.

물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

<그림 1>

<그림 1>은 청소년 상어가 공간에 들어가기 전 초기 상태이다. 상어가 공간에 들어가면 (0, 0)에 있는 7번 물고기를 먹고, 상어의 방향은 ↘이 된다. <그림 2>는 상어가 들어간 직후의 상태를 나타낸다.

<그림 2>

이제 물고기가 이동해야 한다. 1번 물고기의 방향은 ↗이다. ↗ 방향에는 칸이 있고, 15번 물고기가 들어있다. 물고기가 있는 칸으로 이동할 때는 그 칸에 있는 물고기와 위치를 서로 바꿔야 한다. 따라서, 1번 물고기가 이동을 마치면 <그림 3>과 같아진다.

<그림 3>

2번 물고기의 방향은 ←인데, 그 방향에는 상어가 있으니 이동할 수 없다. 방향을 45도 반시계 회전을 하면 ↙가 되고, 이 칸에는 3번 물고기가 있다. 물고기가 있는 칸이니 서로 위치를 바꾸고, <그림 4>와 같아지게 된다.

<그림 4>

3번 물고기의 방향은 ↑이고, 존재하지 않는 칸이다. 45도 반시계 회전을 한 방향 ↖도 존재하지 않으니, 다시 회전을 한다. ← 방향에는 상어가 있으니 또 회전을 해야 한다. ↙ 방향에는 2번 물고기가 있으니 서로의 위치를 교환하면 된다. 이런 식으로 모든 물고기가 이동하면 <그림 5>와 같아진다.

<그림 5>

물고기가 모두 이동했으니 이제 상어가 이동할 순서이다. 상어의 방향은 ↘이고, 이동할 수 있는 칸은 12번 물고기가 있는 칸, 15번 물고기가 있는 칸, 8번 물고기가 있는 칸 중에 하나이다. 만약, 8번 물고기가 있는 칸으로 이동하면, <그림 6>과 같아지게 된다.

<그림 6>

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

입력

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

출력

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.

 

 

 

 

 

 

 

 

 

접근 방법

 

이 문제의 핵심은

상어가 잡아먹을 물고기 칸을 선택할 때, 여러 칸 중 하나를 선택할 수 있으며, 각 선택에 따라 배열 상태가 모두 달라지며 또 그 바뀐 배열에 대해 여러 갈래로 선택지가 나눠진다는 것이다. 이때 가지를 쳐가면서 진행했다가 다시 돌아와야하며 진행 전의 상태로 돌아가야 하는데 이를 어떻게 구현해야할지 어려웠다.

 

그래서 해설을 보고 풀어보았다. 

보통 다른 DFS 알고리즘에서 백트래킹을 할 때는 vector에서 pop 해주는 방식으로 구현했었는데 이 문제에서는 물고기 번호를 나타내는 이차원 배열과 물고기 객체 정보를 담고 있는 1차원 배열, 이 두개의 상태를 저장해줘야 해서 어려웠던것 같다. 

 

그래서 이 문제에서 백트래킹을 구현하기 위해 배열을 복사해서, 복사한 배열의 상태를 변화시켜보고 그 바꾼 배열을 파라미터로 넘겨줌으로써 진행시켜나간다. 이렇게 하면 가지쳐 나간 단계를 한 단계 돌아왔을 때 기존의 배열은 그대로 있기 때문에 이전 단계의 상태를 KEEP 할 수 있게 된다. 

 

 

또 하나 주의할 점은 12시 방향을 의미하는 회전 번호가 1이기 때문에,

처음에 입력받아서 방향 정보를 저장할 때, 1 감소 후 저장하도록 한다. 

이렇게 하면 mod 8 연산을 이용한 방향 회전 구현에 용이하다.  

 

 

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


class Fish {
public:
	int num, dir, r, c;
	bool live;
	Fish(){}
	Fish(int _n, int _d, int _r, int _c, bool _live) {
		num = _n; 
		dir = _d;
		r = _r;
		c = _c;
		live = _live;
	}
};

Fish fishArr[17];	//물고기 1~ 16번까지 객체 저장
int map[4][4];		//물고기 번호만 저장

//12,11,9,,,
int dr[8] = { -1,-1,0,1,1,1,0,-1 };
int dc[8] = { 0,-1,-1,-1,0,1,1,1 };


int ret = 0;

//배열을 함수의 파라미터로 넘길시 Call By Reference (주소값만 넘어감)
void solveDFS(int map[][4], Fish fishArr[], int shark_row, int shark_col, int s) {	

	//백트래킹을 위해 기존 배열 놔두고 카피해서 상태변화 시켜봄
	int copy_map[4][4];
	Fish copy_fishArr[17];
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			copy_map[i][j] = map[i][j];
		}
	}
	for (int i = 0; i < 17; i++ ) {
		copy_fishArr[i] = fishArr[i];
	}


	//물고기 잡아먹기
	int fishNum = copy_map[shark_row][shark_col];
	int shark_dir = copy_fishArr[fishNum].dir;				//잡아먹은 물고기 방향으로 바뀜
	copy_fishArr[fishNum].live = false;
	copy_map[shark_row][shark_col] = -1;						//물고기 잡아먹어서 물고기 없어짐

	s += fishNum;
	if (ret < s) ret = s;




	//물고기 이동
	for (int f = 1; f <= 16; f++) {
		if (copy_fishArr[f].live == false) continue;

		//현재 순서인 물고기의 위치
		int cr = copy_fishArr[f].r;
		int cc = copy_fishArr[f].c;
		int cd = copy_fishArr[f].dir;

		//바꿀 타겟의 위치
		int nr = cr + dr[cd];
		int nc = cc + dc[cd];
		int nd = cd;

		//타겟이 범위 넘어가거나 상어면 회전
		while (nr < 0 || nr >= 4 || nc < 0 || nc >= 4 || (nr == shark_row && nc == shark_col)) {
			nd = (nd + 1) % 8;
			nr = cr + dr[nd];
			nc = cc + dc[nd];
		}

		//1. 타겟 칸이 물고기면

		if (copy_map[nr][nc] != -1) {
			int targetFishNum = copy_map[nr][nc];
			//타겟 물고기 위치 갱신
			copy_fishArr[targetFishNum].r = cr;
			copy_fishArr[targetFishNum].c = cc;

			//현재 물고기 위치 갱신
			copy_fishArr[f].r = nr;
			copy_fishArr[f].c = nc;
			copy_fishArr[f].dir = nd;

			//이차원 배열 번호 swap
			copy_map[nr][nc] = f;
			copy_map[cr][cc] = targetFishNum;

		}


		//2. 타겟 칸이 빈칸이면
		else {

			copy_fishArr[f].r = nr;
			copy_fishArr[f].c = nc;
			copy_fishArr[f].dir = nd;

			copy_map[nr][nc] = f;
			copy_map[cr][cc] = -1;			//원래 물고기 있던 칸은 물고기 없어짐 

		}

	}


	//상어 이동
	for(int step = 1; step <= 3; step++) {
		int nr = shark_row + dr[shark_dir] * step;
		int nc = shark_col + dc[shark_dir] * step;

		if (nr < 0 || nr >= 4 || nc < 0 || nc >= 4) break;

		if (copy_map[nr][nc] != -1) {
			solveDFS(copy_map, copy_fishArr, nr, nc, s);
		}
	}




}



int main() {

	int n, d;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {

			cin >> n >> d;
			Fish fish = Fish(n, d-1, i, j, true);
			map[i][j] = n;		//2차원 배열에 놓기
			fishArr[n] = fish;			//물고기 객체 배열에 넣기

		}
	}



	//상어 초기 셋팅
	ret = 0;
	solveDFS(map, fishArr, 0, 0, 0);
	cout << ret;
	
	return 0;

}


 

 

 

 

참고 블로그 : na982.tistory.com/category/%EC%82%BC%EC%84%B1%20SW%20%EC%97%AD%EB%9F%89%20%ED%85%8C%EC%8A%A4%ED%8A%B8%20%EA%B8%B0%EC%B6%9C%20%ED%92%80%EC%9D%B4?page=2

728x90
728x90

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

 

17779번: 게리맨더링 2

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

www.acmicpc.net

 

 

 

문제

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

재현시는 크기가 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인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.

x = 2, y = 4, d1 = 2, d2 = 2 x = 2, y = 5, d1 = 3, d2 = 2 x = 4, y = 3, d1 = 1, d2 = 1

구역 (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;
}

 

 

 

 

 

 

 

 

728x90
728x90

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

 

17142번: 연구소 3

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고

www.acmicpc.net

 

 

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 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]가 빈칸이 아닌 비활성 상태의 바이러스인 경우이다. 

 

 

0(활성 바이러스)
시작
첫번째 칸에서 이 칸 까지 퍼지는데에 1초 걸림  *(비활성 바이러스)

첫번째 칸에서 이 칸 까지 퍼지는데에 3초 걸림 

* 비활성 바이러스를 활성 바이러스 상태로 바꾸는데에는 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;
}

 

728x90
728x90

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

 

17143번: 낚시왕

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

www.acmicpc.net

 

낚시왕이 상어 낚시를 하는 곳은 크기가 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;
}

 

728x90

+ Recent posts