개발 블로그

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

문제

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

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

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

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

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

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

접근 방법

1) 현재 계단을 밟지 않고 건너 뛰는 경우

2) 현재 계단을 밟는 경우

이렇게 두가지로 나눌 수 있다.

1)번의 경우에 계단의 합의 최대값은 직전의 최대값과 같다. 이 경우엔 현재 계단을 선택하지 않으므로 3개 연속 유무를 신경쓰지 않아도 된다.

2)번의 경우에 계단의 합의 최대값은, 현재 계단을 포함해서 3개 이상 연속되는 경우를 제외해야 한다. 그러므로 직전 계단에서 2개 이상 연속한 경우를 제외하고, 나머지 후보들을 비교해서 최대합을 찾으면 된다.

문제의 입력 예시를 보자.

6개의 계단 값은 10 20 15 25 10 20 이다.

벡터 배열안에 <합, 연속해서 밟은 계단 수> 를 저장했고, 저장할 때마다 합을 비교해서 마지막에 최대합을 dp[]에 저장했다.

벡터 배열 값을 보면 아래와 같다. 

10    vecArr[0] : <0,0>/  <10,1>  -> dp[0] = 10

20   vecArr[1] : <10,0> / <0+20, 1> <10+20, 2>  ->dp[1] = 30

15    vecArr[2] : <30,0> / <10+15, 1> <0+20+15,2>  ->dp[2] =  35

25   vecArr[3] : <35, 0> / <30+25, 1> <10+15+25, 2>  -> dp[3] = 55

10   vecArr[4] : <55,0> / <35+10, 1> <30+25+10, 2>  -> dp[4] = 65

20   vecArr[5] : <65,0> / <55+20, 1> <35+10+20, 2>  -> dp[5] = 75

//
//  DP_BOJ2579_계단오르기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

using namespace std;

int stair[300] = {0};
int dp[300] = {0};
vector<pair<int,int>> vecArr[300];

int main(){
    
    int N; cin >> N;
    for(int i = 0; i<N; i++){
        cin >> stair[i];
    }
    
    //dp[0], dp[1] 초기화
    vecArr[0].push_back(make_pair(0,0));            //-1
    vecArr[0].push_back(make_pair(stair[0],1));     //0
    
    dp[0] = stair[0];
    
    vecArr[1].push_back(make_pair(dp[0], 0));               //0 x
    vecArr[1].push_back(make_pair(stair[1], 1));            //x 1
    vecArr[1].push_back(make_pair(stair[0] + stair[1], 2)); //0 1
    
    int maxi=0;
    for(int i = 0; i<3; i++){
        if(maxi<vecArr[1][i].first) maxi = vecArr[1][i].first;
    } dp[1] = maxi;
    
    
    
    for(int i = 2; i<=N-1; i++){
        
        //case 1 : 현재 계단 안 밟는 경우
        if(i!=N-1){     //문제의 조건에서 마지막 계단은 무조건 밟는다고 했음
            vecArr[i].push_back(make_pair(dp[i-1], 0));     //직전 계단까지 왔을 때 최대값
        }
        
        //case 2 : 현재 계단 밟는 경우
        int maxi = 0;
        for(int j = 0; j<vecArr[i-1].size(); j++){
            int conti = vecArr[i-1][j].second;
            if(conti==2) continue;                  //직전 계단까지 2개 연속해서 밟은 경우, 3개 연속 못 밟음
            
            int sum = stair[i] + vecArr[i-1][j].first;
            if(maxi < sum) maxi = sum;
            vecArr[i].push_back(make_pair(sum,conti+1));    //현재 계단 밟았으므로 연속해서 밟은 계단 수 1증가해서 저장
 
        }
        dp[i] = maxi;
        
    }
    cout << dp[N-1];
    
    return 0;
}

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

문제

0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다. 다음 예를 보자.

26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = 12이다. 새로운 수는 42이다. 4+2 = 6이다. 새로운 수는 26이다.

위의 예는 4번만에 원래 수로 돌아올 수 있다. 따라서 26의 사이클의 길이는 4이다.

N이 주어졌을 때, N의 사이클의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 0보다 크거나 같고, 99보다 작거나 같은 정수이다.

출력

첫째 줄에 N의 사이클 길이를 출력한다.

접근 방법

알고리즘 분류는 문자열이지만 그냥 정수형으로 입력 받아서 나눗셈 연산을 이용해서 해결했다.

//
//  문자열_BF1110_더하기사이클.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string>

using namespace std;


int main(){
    
    int num, num1, num2, ans=0;
    cin >> num;
    
    if(num<10) {
        num1 = 0;
        num2 = num;
    }
    else{
        num1 = num/10;
        num2 = num-num1*10;
    }
    
    while(1){
        ans+=1;
       
        int sum = num1 + num2;
        if(sum>9){
            int q = sum/10;
            sum = sum-q*10;
        }
        
        int newNum = num2*10 + sum;
        if(newNum==num) {
            break;
        }
        else{
            num1 = newNum/10;
            num2 = newNum - num1*10;
        }
    }
        
    cout << ans;
        
    return 0;
}

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

문제

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

접근 방법

1) 기본 DFS + 기본 BFS -> 시간 초과

처음에는 DFS로 치킨 집 중 M개를 선택하고, 선택이 완료되면 BFS로 각 집에서 치킨집까지 최소 거리를 구했다. 그랬더니 답은 제대로 나왔지만 시간 초과가 떴다.

2) 기본 DFS + BFS 사용x -> 시간 초과

M의 최대가 13밖에 안되니 BFS 대신 직접 각 집에서 치킨집까지 거리를 abs()를 이용해서 구했다.

3) 중복조합으로 DFS 개선 + BFS 사용x -> 통과

치킨 집을 2개 선택한다 했을 때, <1번, 2번> 이나 <2번, 1번>이나 같으므로 중복 조합을 이용했다.

//
//  BF_BOJ15686_치킨배달.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string.h>
#include <queue>
#include <cmath>
using namespace std;

int N, M;

int map[51][51];
int fromStart[51][51];
int newMap[51][51];
vector<pair<int,int>> homeVec;       //1
vector<pair<int,int>> chickenVec;   //2
int visited[100] = {0};
vector<pair<int,int>> pickedChick;   //2중 M개 선택

//위 오 아 왼
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};
int mini = 100000000;
int answer =100000000;


void pickChickDFS(int toPick, int start){

    if(toPick==0){
        
        int sum=0;
        //각 집에서 pickChick까지의 거리들 중 최소값들의 합
        for(int i = 0; i<homeVec.size();i++){
            mini = 100000000;
            
            for(int j = 0; j<pickedChick.size(); j++){
                int dis = abs(homeVec[i].first-pickedChick[j].first)
                + abs(homeVec[i].second - pickedChick[j].second);
                
                if(mini>dis) mini = dis;
            }
            sum+=mini;
            if(sum>answer) return;
        }
        
        if(answer>sum) answer = sum;
        return;
    }
    
    for(int i = start; i<chickenVec.size(); i++){
        if(visited[i]==0){
            visited[i] = 1;
            pickedChick.push_back(chickenVec[i]);
            pickChickDFS(toPick-1, i);
            pickedChick.pop_back();
            visited[i] = 0;
        }
    }
}


int main(){
    cin >> N >> M;
    
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=N; j++){
            cin >> map[i][j];
            if(map[i][j]==1){   homeVec.push_back(make_pair(i,j)); }
            if(map[i][j]==2){   chickenVec.push_back(make_pair(i,j)); }
        }
    }
    
    pickChickDFS(M, 0);
    cout << answer;
    
    return 0;
}