대엉코딩

www.acmicpc.net/problem/17143

1. 풀이방법

- 비교적 간단한 구현 문제입니다.

- 1단계가 낚시왕의 이동, 2단계가 낚시, 3단계가 상어의 이동입니다.

- 1,2 단계는 매우 쉽고, 3단계에서 최대 상어의 마리수 M =10000이고, 한번에 이동할 수 있는 칸은 최대 1000칸 이므로

- 한칸씩 상어를 이동시킬 경우 10000000 에, 다른 부가적인 작업들이 들어가면 시간초과 가능성이 있다고 판단하여

- 문제의 사진을 잘 분석해 보면 한칸씩 이동시키는 것이 어떤 수가 되었을 때 정확히 같은방향, 같은 자리로 오는지를 

- 파악해보면, ( 2 * ((R or C)-1) ) 칸을 움직이면 같은방향을 가지면서 같은 자리로 이동합니다.

- 즉 최종으로 한칸씩 이동시킬 fixedmovecount= speed % ( 2 * ((R or C)-1) ) 만큼만 한칸 씩 이동시키면 됩니다.

2. 주의사항

- 모듈러연산을 활용한다 정도?

- 문제도 짧고 헷갈릴만한 단어도 딱히 없었습니다...

3. 나의코드

#include<bits/stdc++.h>
using namespace std;
int R, C,M;
struct shark {
	int speed, dir, ssize,num;
};
vector<shark> sea[102][102];
vector<pair<int, int>> sharkvec; // 상어들의 위치 저장
bool sharkdie[10001]; // 상어 살았는지 여부 조사
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 };
int sharksum;

void inputs() {
	cin >> R >> C>>M;
	int r, c, s, d, z;
	for (int i = 0; i < M; i++) {
		cin >> r >> c >> s >> d >> z;
		sharkvec.push_back({ r,c });
		sea[r][c].push_back({ s,d - 1,z,i });
	}
}
void getshark(int f) {
	for (int i = 1; i <= R; i++) {
		if (!sea[i][f].empty()) {
			sharksum += sea[i][f][0].ssize; //잡음
			sharkdie[sea[i][f][0].num] = true;
			sea[i][f].pop_back();
			return;
		}
	}
	return;
}

void moveshark() {
	vector<shark> tmpsea[102][102];
	for (int i = 0; i < M; i++) {
		if (sharkdie[i]) continue; //죽었으면 보지않음

		int x = sharkvec[i].first; int y = sharkvec[i].second;
		int tmps, tmpd, tmpz;
			tmps = sea[x][y][0].speed;
			tmpz = sea[x][y][0].ssize; //크기
			tmpd = sea[x][y][0].dir;


		int fixexmovecount;
		if (tmpd <= 1) { // 세로이동
			fixexmovecount = tmps%(2*(R - 1));
			for (int a = 0; a < fixexmovecount; a++) {
				if (x == R) { tmpd = 0; }
				if (x == 1) { tmpd = 1; }
				x += dx[tmpd];
			}
		}
		else { //가로이동
			fixexmovecount = tmps%(2*(C - 1));
			for (int a = 0; a < fixexmovecount; a++) {
				if (y == C) { tmpd = 3; }
				if (y == 1) { tmpd = 2; }
				y += dy[tmpd];
			}
		}
		sharkvec[i].first = x; sharkvec[i].second = y;
		if(tmpsea[x][y].empty()) tmpsea[x][y].push_back({ tmps,tmpd,tmpz,i }); //아무도 없으면 그냥 삽입
		else { //다른 상어가 있으면 큰놈이 작은놈을 잡아먹는다
			if (tmpsea[x][y][0].ssize < tmpz) {
				sharkdie[tmpsea[x][y][0].num] = true; // 기존에 있던놈 잡아먹힘
				tmpsea[x][y].pop_back();
				tmpsea[x][y].push_back({ tmps,tmpd,tmpz,i });
			}
			else { //넣으려던놈이 잡아먹힘
				sharkdie[i] = true;
			}
		}
	}
	for (int t = 1; t <= R; t++) {
		for (int k = 1; k <= C; k++) {
			sea[t][k] = tmpsea[t][k];
		}
	}
	return;
}
/*void watchshark() {
	cout << "\n";
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (sea[i][j].empty()) cout << 0 << " ";
			else cout << sea[i][j][0].num+1 << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}*/
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	for (int fm = 1; fm <= C; fm++) { // 낚시꾼의 위치 (1초당)
		getshark(fm);
		moveshark();
	}
	cout << sharksum;


	return 0;
}

www.acmicpc.net/problem/17822

1. 풀이방법

- 구현문제입니다.

- circular의 특성만 체크 해서 0이 될경우 M으로 바꿔주고 M+1이 될경우 1로 바꿔주는 것에 신경써주고,

- 문제에서 구현하라는 대로 하시면 됩니다.

- bfs를 통해서 인접한 수 들을 모두 지워주었습니다.

2. 주의사항

- 평균에 대한 특별한 언급이 없어서( 나머지는 버린다던가...) 

- 그냥 double형으로 선언하여 평균을 구해주었더니 맞았습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int N, M, T; // 반지름, 원판당 수, T번 회전시킨다.
int circle[51][51]; // 몇번째 원/ 몇번째 수
bool visited[51][51]; //bfs를 위한 
queue<pair<int, int>> tmpq;
int xi, di, ki;
int xdk[51][3];
bool checkexist = false;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
double tmpsum, tmpn;
bool neighbor = false;

//번호가 xi의 배수인 원판을 di방향(0-시계,1-반시계) ki칸 만큼 회전
void inputs() {
	cin >> N >> M >> T;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> circle[i][j];
		}
	}
	for (int i = 1; i <= T; i++) {
		cin >> xdk[i][0] >> xdk[i][1] >> xdk[i][2];
	}
}
bool boundcheck(int x) {
	return (x >= 1 && x <= N); //원의 범위
}
void rotate(int r) {
	for (int k = 0; k < xdk[r][2]; k++) {
		for (int i = 1; i <= N; i++) {
			if (i % xdk[r][0] != 0) continue; // xi의 배수인 원판만 회전

			int tmpnum;
			if (xdk[r][1] == 0) { // 시계방향
				tmpnum = circle[i][M];
				for (int j = M; j >= 2; j--) {
					circle[i][j] = circle[i][j - 1];
				}
				circle[i][1] = tmpnum;
			}
			else { //반시계방향
				tmpnum = circle[i][1];
				for (int j = 1; j < M; j++) {
					circle[i][j] = circle[i][j + 1];
				}
				circle[i][M] = tmpnum;
			}
		}
	}
}
void initvisit() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			visited[i][j] = false;
		}
	}
}
void bfs(int x, int y) {
	visited[x][y] = true;
	tmpq.push({x,y});
	while (!tmpq.empty()) {
		int qsize = tmpq.size();
		while (qsize--) {
			int nextx = tmpq.front().first;
			int nexty = tmpq.front().second;
			tmpq.pop();
			for (int i = 0; i < 4; i++) {
				int tx = nextx + dx[i]; int ty = nexty + dy[i];
				if (ty == 0) ty = M; //circular
				if (ty == M + 1) ty = 1;
				
				if (boundcheck(tx) && !visited[tx][ty] && circle[tx][ty] == circle[x][y]) {
					tmpq.push({ tx,ty });
					visited[tx][ty] = true;
					neighbor = true;
					circle[tx][ty] = 0; //지우기
					checkexist = true;
				}
			}
		}
	}
	if (neighbor == true) {
		circle[x][y] = 0; 
	} //하나라도 존재하면 여기도 지우기 (시작점)
}
void getsum() {
	tmpsum = 0; tmpn = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (circle[i][j] != 0) {
				tmpsum += circle[i][j];
				tmpn++;
			}
		}
	}
}
/*void watchcircle() {
	cout << "\n";
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cout << circle[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}*/
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs(); //원판 셋팅
	for(int a=1;a<=T;a++) {
		rotate(a); //회전
		getsum(); // 전체 존재의 수와 그들의 합
		if (tmpn == 0) { cout << 0; return 0; }
		initvisit();
		checkexist = false; // 인접하면서 같은 수가 하나라도 존재하는지 체크
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				neighbor = false; //이웃이 하나라도 있으면 삭제되고 아니면 지워지지 않음
				if (circle[i][j] != 0 && visited[i][j] == false) {
					bfs(i, j);
				} // 인접
			}
		}
		if (checkexist == false) { //인접한 수가 존재하지 않을 때
			double avg = tmpsum / tmpn;
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= M; j++) {
					if (circle[i][j] == 0) continue;

					if (circle[i][j] > avg) {
						circle[i][j]--; continue;
					}
					else if (circle[i][j] < avg) {
						circle[i][j]++; continue;
					}
				}
			}
		}
	}
	int resultsum = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			resultsum += circle[i][j];
		}
	}
	cout << resultsum;
	return 0;
}

www.acmicpc.net/problem/17825

1. 풀이방법

- 쉽다고 생각하면서 , 시작해서 개고생하며 어렵게 끝낸 문제입니다.....

- 첫번째 문제점, 30 노드가 중복되는 것을 체크하지 못한점.

- 30 노드에 도착하면 방향을 바꾸도록 설정했다가 다른 30 (끝 쪽에 가까운) 거기에 말들이 도착헀을때도 방향을 바꾸는 현상 발생.

- 두번째 문제점, 방문체크를 할때 여러개 있는 노드들을 고려하지 않은 것.

- 문제를 보면, 두개이상 존재하는 노드들이 있다 (16, 22,28,30.....)

- 결국 현재 말들의 위치만을 비교함으로써 겹쳐지는지 아닌지 알 수 가 없다.

- 결국 코드를 싹 지우고, 다시 짜면서 해결한 방법은

- 각각 고유의 번호를 가지는 노드들로 같은 모양의 그래프를 만들어 준 후, 문제에서의 노드들은 점수들로서

- 매칭을 시켜주었습니다. 그러면 첫, 두 번째 문제점들이 모두 해결됩니다.

- 그림을 보시면 아이디어를 이해하시기 편할 겁니다.

- 전체적인 문제해결은 dfs를 이용한 완전탐색 입니다.

2. 주의사항

- 일단 코드를 작성하기 전, 문제를 항상 정확히 파악하고 시작하고자 노력하지만

- 이 문제처럼, 처음 시작할 때 발생하는 문제를 예상하지 못하고 시작하면 굉장히 어려워 지고 꼬입니다....

- 역시, 주의사항은...... 문제를 꼼꼼히 잘 분석하자......

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

// 시작노드 0, 도착점 노드 21
int route[4][33];
int score[33]; // 점수계산을 위한 노드
int maxresult;
int inputnum[10];
pair<int, int> ob[4]; //4개의말 (현재위치, 타고있는 방향)

void inputs() {
	for (int i = 0; i < 10; i++) {
		cin >> inputnum[i];
	}
}
void setscore() {
	for (int i = 1; i <= 20; i++) {
		score[i] = 2 * i;
	}
	score[22] = 13; score[23] = 16; score[24] = 19;
	score[25] = 25; score[30] = 26; score[29] = 27;
	score[28] = 28; score[26] = 22; score[27] = 24;
	score[31] = 30; score[32] = 35; score[21] = 0;
}
void makegraph() {
	for (int i = 0; i < 21; i++) {
		route[0][i] = i + 1;
	}
	route[0][21] = 21;
	route[1][5] = 22; route[1][22] = 23; route[1][23] = 24;
	route[1][24] = 25; route[1][25] = 31; route[1][31] = 32;
	route[1][32] = 20; route[1][20] = 21; route[1][21] = 21;
	route[2][10] = 26; route[2][26] = 27; route[2][27] = 25;
	route[2][25] = 31; route[2][31] = 32; route[2][32] = 20;
	route[2][20] = 21; route[2][21] = 21;
	route[3][15] = 28; route[3][28] = 29; route[3][29] = 30;
	route[3][30] = 25; route[3][25] = 31; route[3][31] = 32;
	route[3][32] = 20; route[3][20] = 21; route[3][21] = 21;
}
bool existcheck(int s,int index) {
	if (s == 21) return false;
	for (int i = 0; i < 4; i++) {
		if (i == index) continue;
		if (ob[i].first == 21) continue;
		if (ob[i].first == s) return true;
	}
	return false;
}
void makecase(int cnt,int resultsum) {
	if (cnt == 10) {
		maxresult = max(resultsum, maxresult);
		return;
	}
	int thisnum = inputnum[cnt];
	for (int i = 0; i < 4; i++) {
		if (ob[i].first == 21) continue; //이미 도착점에 있는 말
		int prevnum = ob[i].first;
		int prevdir = ob[i].second;
		for (int j = 0; j < thisnum; j++) {
			ob[i].first = route[prevdir][ob[i].first];
		}
		if (ob[i].first == 5) ob[i].second = 1;
		if (ob[i].first == 10) ob[i].second = 2;
		if (ob[i].first == 15) ob[i].second = 3;

		if (!existcheck(ob[i].first,i)) {
			makecase(cnt + 1, resultsum + score[ob[i].first]);
		}
		ob[i].first = prevnum;
		ob[i].second = prevdir;

	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	setscore();
	makegraph();
	makecase(0,0);
	cout << maxresult;
	return 0;
}

www.acmicpc.net/problem/17837

1. 풀이방법

- 구현문제입니다.

- 문제의 조건대로 출력해주면 됩니다.

- 자료형을 잘 생각해서 문제풀이 시작에 들어가면 됩니다.

2. 주의사항

- 아무리봐도 맞는데, 마지막 테케가 원하는 대로 안나오고 -1이 나왔습니다.

- 문제를 잘 읽어보니 종료조건을 TURN 이 증가 될때마다가 아닌, 한마리의 말을 이동시킬 때 마다 종료조건을 검사해야 합니다. 

-왜냐하면, 높이가 4이상이 되는 순간 (게임이 진행되는 도중) 바로 게임이 종료되기 때문입니다.

3. 나의 코드

#include<bits/stdc++.h>
using namespace std;

int N, K;

int ground[14][14];
vector<pair<int,int>> chess[14][14]; //쌓이는 말들을 표시하기 위에 맨앞=맨아래 (번호, 이동방향)
vector<pair<int, int>> horse; //그말은 아니지만;;ㅎ

int dx[4] = { 0,0,-1,1 }; //1234
int dy[4] = { 1,-1,0,0 };

void inputs() {
	cin >> N >> K;
	for (int i = 0; i <= N + 1; i++) { //테두리는 파란색 취급
		ground[0][i] = 2;
		ground[i][0] = 2;
		ground[N + 1][i] = 2;
		ground[i][N + 1] = 2;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> ground[i][j];
		}
	}
	horse.push_back({ -1,-1 }); //index 맞추기 용

	int x, y, z;
	for (int i = 1; i <= K; i++) {
		cin >> x >> y >> z;
		chess[x][y].push_back({ i, z-1 });
		horse.push_back({ x,y }); //말의 위치 표시
	}
}
bool checkexit() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (chess[i][j].size() >= 4) return true;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	int turncount = 0;
	while (1) {

		turncount++;
		//1번말부터 이동
		for (int i = 1; i <= K; i++) {
			int tx = horse[i].first; int ty = horse[i].second; // 그 말의 위치
			for (int j = 0; j < chess[tx][ty].size(); j++) {
				if (chess[tx][ty][j].first == i) { //쌓여있는 말의 위치를 알았다.

					int tmpdir = chess[tx][ty][j].second; //이동방향
					int nextx = tx + dx[tmpdir]; int nexty = ty + dy[tmpdir];


					if (ground[nextx][nexty] == 0) { //흰색
						int erasecount = 0;
						for (int k = j; k < chess[tx][ty].size(); k++) {
							chess[nextx][nexty].push_back(chess[tx][ty][k]);
							horse[chess[tx][ty][k].first] = { nextx,nexty }; //말의 위치가 바뀐걸 알려줘야 한다.
							erasecount++;
						}
						while (erasecount--) { //이동헀으니 제거
							chess[tx][ty].pop_back(); 
						}
						break;
					}

					else if (ground[nextx][nexty] == 1) { //빨간
						int erasecount = 0;
						for (int k = chess[tx][ty].size() - 1; k >= j; k--) {
							chess[nextx][nexty].push_back(chess[tx][ty][k]);
							horse[chess[tx][ty][k].first] = { nextx,nexty };
							erasecount++;
						}
						while (erasecount--) {
							chess[tx][ty].pop_back();
						}
						break;
					}
					else { //파란
						//이동방향 반대로

						if (tmpdir == 0) tmpdir = 1;
						else if (tmpdir == 1) tmpdir = 0;
						else if (tmpdir == 2) tmpdir = 3;
						else tmpdir = 2;

						chess[tx][ty][j].second = tmpdir;

						if (ground[tx + dx[tmpdir]][ty + dy[tmpdir]] == 2) { //반대도 파란색
							break;
						}
						else {
							j--;
						}// 한번 더 반복
					}
				}
			}
			//순간 이므로 !
			if (checkexit()) { cout << turncount; return 0; }
		}
		if (turncount > 1000) { cout << -1; return 0; }
	}
}

www.acmicpc.net/problem/16235

1. 풀이방법

- 단순한 구현 문제입니다.

- 문제는 간단하고 이해도 어렵지 않지만, 시간제한이 0.3초 인 점을 감안하여야 합니다.

- 문제에서의 단계대로 차례차례 진행해줍니다.

2. 주의사항

- 전 처음에 시간제한 및 어린나이부터 진행되어야 한다는 문제를 보고 우선순위 큐를 생각해서 접근하였는데,

- 정답은 잘 뽑아내는 것 같으나, 시간초과가 계속 되어 결국 자료형을 vector로 바꿔서 봄에만 정렬을 하여 사용하였습니다.

- vector를 사용하자니, 죽은 나무를 뽑아내는 것이 문제였는데, vector는 index로 쉽게 접근이 가능하나 원하는 위치의데이터를 맘대로 뽑기는 어렵습니다.

- 그래서 양분이 부족해지는 지점이 딱 왔을 때, 그 이차원벡터배열의 맨뒤부터 양분/2를 더해주면서 pop_back() 해주었습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int n, m, K;
int ground[11][11]; // 양분의 양
vector<int> treeageset[11][11]; //나이 기준 정렬
int s2d2[11][11];
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
int tmpv[1001];
int presize[11][11]; 

void inputs() {
	cin >> n >> m >> K;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ground[i][j] = 5;
			cin >> s2d2[i][j];
		}
	}
	int x, y, z;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		treeageset[x][y].push_back(z);
	}
}
bool boundcheck(int x, int y) {
	return (x >= 1 && x <= n && y >= 1 && y <= n);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	for (int i = 0; i < K; i++) { //1년

		//봄
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (treeageset[j][k].empty()) continue;
				int tmpground = ground[j][k];
				ground[j][k] = 0;
				sort(treeageset[j][k].begin(), treeageset[j][k].end());
				int vsize = treeageset[j][k].size();
				for (int a = 0; a < vsize; a++) {
					if (tmpground >= treeageset[j][k][a]) {
						tmpground -= treeageset[j][k][a];
						treeageset[j][k][a]++;
					}
					else {
						for (int b = vsize - 1; b >= a; b--) {
							ground[j][k] += treeageset[j][k][b] / 2;
							treeageset[j][k].pop_back();
						}
						break;
					}
				}
				ground[j][k] += tmpground; //남은 양분+죽은나무의 양분
			}
		}


	//새로 추가되는 나무들은 번식시키지 않기 위해서
	for (int j = 1; j <= n; j++) { 
		for (int k = 1; k <= n; k++) {
			presize[j][k] = treeageset[j][k].size();
		}
	}
	//가을 번식
	for (int j = 1; j <= n; j++) {
		for (int k = 1; k <= n; k++) {
			for (int a = 0; a < presize[j][k]; a++) {
				if (treeageset[j][k][a] % 5 == 0) {
					for (int b = 0; b < 8; b++) {
						int nextx = j + dx[b];
						int nexty = k + dy[b];
						if (boundcheck(nextx, nexty)) {
							treeageset[nextx][nexty].push_back(1);
						}
					}
				}
			}
			ground[j][k] += s2d2[j][k]; //양분 보급
		}
	}
}
	int resultsum = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			resultsum += treeageset[i][j].size();
		}
	}
	cout << resultsum;
	return 0;
}

www.acmicpc.net/problem/17779

1. 풀이방법

- 구현문제입니다.

- 나머지 선거구는 문제에서 이미 범위가 다 주어져서 쉬운 문제입니다.

- 문제는 5번선거구를 처리하는 것입니다.

- 저는 가장자리를 먼저 구해서 맵에 체크 해놓고, (x+1,y) 좌표를 기준으로 bfs를 돌린 뒤, 4면이 다 5선거구로 둘러쌓여 있는 지역을 5번 선거구에 포함하여 주었습니다.

- 0 5 0 0 0

  5 0 5 0 0

  0 5 0 5 0

  0 0 5 0 0

- 위와 같은 예시는 4방향탐색 bfs로는 5선거구에 포함시킬 수 없기 때문입니다.

2. 주의사항

- 문제조건에 왠만하면 범위를 맞추자.... (0~n-1)로 고집하지말고... 1~n으로 맞춰서 하자....

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

pair<int, int> ground[22][22]; //first =선거구, second= 구역별 인원
int n;
queue<pair<int, int>> tmpq;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int numcount[6];
int resultmin = 20000;

void inputs() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> ground[i][j].second;
		}
	}
}
bool boundcheck(int i, int j, int a, int b) {
	return ((i + a + b) <= n && (j - a >= 1) && (j + b <= n));
}
void initground() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ground[i][j].first = 0;
		}
	}
}
bool bfsboundcheck(int x, int y) {
	return (x <= n&& x >= 1 && y >= 1 && y <= n);
}
void bfs(int x, int y) {
	ground[x][y].first = 5;
	tmpq.push({ x,y });
	while (!tmpq.empty()) {
		int qsize = tmpq.size();
		while (qsize--) {
			int nextx = tmpq.front().first;
			int nexty = tmpq.front().second;
			tmpq.pop();
			for (int i = 0; i < 4; i++) {
				int tx = nextx + dx[i];
				int ty = nexty + dy[i];
				if (bfsboundcheck(tx, ty) && ground[tx][ty].first != 5) {
					tmpq.push({ tx,ty });
					ground[tx][ty].first = 5;
				}
			}
		}
	}
}

void makeoutside(int x,int y,int d1,int d2) {
	// 일단 경계선
	for (int i = 0; i <= d1; i++) {
		ground[x + i][y - i].first = 5;
		ground[x + d2 + i][y + d2 - i].first = 5;
	}
	for (int j = 0; j <= d2; j++) {
		ground[x + j][y + j].first = 5;
		ground[x + d1 + j][y - d1 + j].first = 5;
	}
	//bfs 돌리고 + 4면이 모두 5인 곳은 따로 체크
	if (ground[x + 1][y].first == 0) bfs(x + 1, y);
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < n; j++) {
			int tmpcount = 0;
			for (int k = 0; k < 4; k++) {
				if (ground[i + dx[k]][j + dy[k]].first == 5) {
					tmpcount++;
				}
				else break;
			}
			if (ground[i][j].first != 5 && tmpcount == 4) { ground[i][j].first = 5; }
		}
	}
	for (int i = 1; i < x + d1; i++) { //1번 선거구
		for (int j = 1; j <= y; j++) {
			if (ground[i][j].first == 5) continue;
			ground[i][j].first = 1;
		}
	}
	for (int i = 1; i <= x + d2; i++) { //2번 선거구
		for (int j = y+1; j <= n; j++) {
			if (ground[i][j].first == 5) continue;
			ground[i][j].first = 2;
		}
	}
	for (int i = x + d1; i <= n; i++) { //3번 선거구
		for (int j = 1; j < y - d1 + d2;j++) {
			if (ground[i][j].first == 5) continue;
			ground[i][j].first = 3;
		}
	}
	for (int i = x + d2+1; i <= n; i++) {
		for (int j = y - d1 + d2; j <= n; j++) {
			if (ground[i][j].first == 5) continue;
			ground[i][j].first = 4;
		}
	}
}
void numcheckreset() {
	for (int i = 1; i <= 5; i++) {
		numcount[i] = 0;
	}
}
void getnumcount() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			numcount[ground[i][j].first] += ground[i][j].second;
		}
	}
}
bool emptycheck() {
	for (int i = 1; i <= 5; i++) {
		if (numcount[i] == 0) return true;
	}
	return false;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	inputs();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int a = 1; a <= n; a++) {
				for (int b = 1; b <= n; b++) {
					if (boundcheck(i, j, a, b)) { //범위를 만족할 때만
						initground();
						makeoutside(i,j,a,b);
						numcheckreset();
						getnumcount();
						if (emptycheck()) continue; //적어도 하나의 구역 포함
						sort(numcount + 1, numcount + 6);
						resultmin = min(resultmin, numcount[5] - numcount[1]);
					}
				}
			}
		}
	}
	cout << resultmin;
	return 0;
}

www.acmicpc.net/problem/19237

1. 풀이방법

- 사실 풀이방법은 딱히 없습니다...

- 문제에서 원하는 조건 그대로를 구현해내면되고, 사용되는 알고리즘 또한 별로 없는 것 같다.

- 조건을 한단계씩 맞춰나가면서 스텝 바이 스텝으로 짜면 되는데,,,,,,,, 코드가 매우 길어집니다.. 저만 그런건지.....

2. 주의사항

- *** 처음에 문제를 천천히 파악하고 문제의 조건들을 충분히 담을 수 있을만한 자료구조와 변수 선언에 신경써야합니다.짜다 보니 이 변수들로만 모든걸 체크하기 부족해서 추가적으로 임의로 선언할 경우 코드가 길어지면서 실수할 가능성이 높은 것 같습니다.

 그래서 이 과정에 꽤 많은 시간을 소모해도 된다고 생각합니다.

- 단계,단계 차례대로 천천히 구현해 나갈 것

- 저 같은 경우 마지막에 다 짰는데도 틀렸습니다가 떠서 봤더니...

  비슷한 변수이름을 두개 (sharkdir, sharkdir) 을 선언해서 썼더니 코드가 길어지면서 저도 모르게 이를 실수 했습니다.

  왠만하면 변수이름은 잘 구별될 수 있도록 선언하는 것이 좋을 것 같습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int n,m,k;
bool sharkdie[401];
vector<int> sharkdir;
pair<int, int> sharks[401]; //현재 상어들의 위치 (x,y)
vector<pair<int, int>> sea[21][21]; //first= 상어번호, second= 남은 k
int dirinfo[401][4][4];
int tmpint;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
//위.아래,왼쪽,오른쪽
void inputs() {
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> tmpint;
			if (tmpint != 0) {
				sharks[tmpint].first = i; sharks[tmpint].second = j;
			}
		}
	}
	sharkdir.push_back(-1); // 인덱스 맞추기 용
	for (int i = 0; i < m; i++) {
		cin >> tmpint; sharkdir.push_back(tmpint-1); 
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				cin >> tmpint;
				dirinfo[i][j][k]=tmpint-1;
			}
		}
	}
}
bool boundcheck(int x, int y) {
	return (x >= 0 && y >= 0 && x < n&& y < n);
}
bool checksharks() {
	for (int i = 2; i <= m; i++) {
		if (sharkdie[i] == false) return false;
	}
	return true; //1번 상어 빼고 다 쫓겨남
}
int main() {
	inputs();
	int resultsecond=0;
	while (1) {
		if (resultsecond > 1000) { cout << -1; break; }
		if (checksharks()) { cout << resultsecond; break; }


		//냄새 k 감소
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!sea[i][j].empty()) {
					sea[i][j][0].second--;
					if (sea[i][j][0].second == 0) {
						sea[i][j].clear();
					}
}
			}
		}

		//냄새 뿌리기
		for (int i = 1; i <= m; i++) {
			if (sharkdie[i] == false) { //쫓겨나지 않았다면 냄새 뿌린다.
				sea[sharks[i].first][sharks[i].second].clear();
				sea[sharks[i].first][sharks[i].second].push_back({ i,k });
			}
		}

		//이동하기
		for (int i = 1; i <= m; i++) { //상어 한마리씩 본다.
			if (sharkdie[i] == true) continue;
			bool suc = false;
			// 냄새가 없는 칸이 있는지 먼저본다.
			for (int j = 0; j < 4; j++) {
				int nextx = sharks[i].first + dx[dirinfo[i][sharkdir[i]][j]];
				int nexty = sharks[i].second + dy[dirinfo[i][sharkdir[i]][j]];
				if (boundcheck(nextx, nexty) && sea[nextx][nexty].empty()) { //냄새가 없는 칸
					sharks[i].first = nextx;
					sharks[i].second = nexty;
					suc = true;
					sharkdir[i] = dirinfo[i][sharkdir[i]][j]; //이동한 방향이 보고있는 방향이 된다.
					break;
				}
			}
			
			if (suc == false) {
				for (int j = 0; j < 4; j++) {
					int nextx = sharks[i].first + dx[dirinfo[i][sharkdir[i]][j]];
					int nexty = sharks[i].second + dy[dirinfo[i][sharkdir[i]][j]];
					if (boundcheck(nextx, nexty) && sea[nextx][nexty][0].first == i) { //자신의 냄새가 있는 칸
						sharks[i].first = nextx;
						sharks[i].second = nexty;
						suc = true;
						sharkdir[i] = dirinfo[i][sharkdir[i]][j]; //이동한 방향이 보고있는 방향이 된다.
						break;
					}
				}
			}
		}



		// 겹치는 상어 쫓아내기
		for (int i = 1; i <= m; i++) {
			if (sharkdie[i] == true) continue;
			for (int j = i + 1; j <= m; j++) {
				if (sharkdie[j] == true) continue;
				if (sharks[i].first == sharks[j].first && sharks[i].second == sharks[j].second) { // 겹쳐진 상어가 생기면
					sharkdie[j] = true; // 쫓겨난다 (번호가 늦는 놈이)
				}
			}
		}
		resultsecond++;
	}
	return 0;
}

www.acmicpc.net/problem/17140

1. 풀이방법

- 구현 문제이고, 일단 문제를 이해를 잘해야합니다....

- 읽으면서도 이게 무슨말이지 싶고, 예시로 주어진 것들을 써보고 규칙을 정확히 이해해야 합니다.

- 읽으면서도 처음에는 숫자가 먼저 쭉 들어가고 등장횟수가 새로 배열에 들어가는 줄 알았으나 예시가 이상해서 보니

- (수, 등장횟수, 수, 등장횟수, 수 등장횟수...) 이런 순입니다

- 정렬순서를 구현했고 이차원배열로 max 범위로 잡아놓고 현재의 행의 수, 열의 수 를 관리하는 변수 두개를 두어

- 관리 하였습니다. 특별히 어려운 사항은 없었던 것 같습니다.

2. 주의사항

- 가끔 예제를 돌리다가 걸리는 사항인데, 저는 보통 n이면 0~n-1만큼을 사용합니다.

- 즉 문제에서 [r][c]를 원하면 저의 배열에서는 [r-1][c-1]의 값인거죠~!

- 여담이였고, 이 문제는 그냥 문제 자체만 잘 이해하면 되는 것 같습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int r, c, k;
int ground[101][101];
int hang = 3; //현재 행의 수
int yull = 3; //현재 열의 수
struct xx {
	int xnum;
	int totalcount;
};


void inputs() {
	cin >> r >> c >> k;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> ground[i][j];
		}
	}
}
bool compare(xx t1, xx t2) {
	if (t1.totalcount < t2.totalcount) return true;
	if (t1.totalcount == t2.totalcount) {
		if (t1.xnum < t2.xnum) return true;
		else return false;
	}
	else return false;
}

void Rcal() {
	int maxyull = 0;
	vector<int> tmpcount; //각 행의 수를 저장해두었다가 max-tmpcount[i] 만큼 0으로채우려고
	for (int i = 0; i < hang; i++) { //모든 행에 대하여
		int tmpyull = yull;
		vector<xx> xarr;
		for (int j = 0; j < tmpyull; j++) {
			if (ground[i][j] == 0) continue;
			bool c = false;
			for (int k = 0; k < xarr.size(); k++) { // 이미 있는지 확인
				if (ground[i][j] == xarr[k].xnum) {
					xarr[k].totalcount++; c = true; break;
				}
			}
			if (c == false) { //위에서 안걸러 졌으면
				xarr.push_back({ ground[i][j],1 });
			}
		}
		sort(xarr.begin(), xarr.end(), compare); //정렬
		tmpyull = xarr.size() * 2; // 새로운 열의 사이즈가 됨
		for (int j = 0; j < tmpyull; j++) {
			ground[i][j] = xarr[j / 2].xnum;
			ground[i][j + 1] = xarr[j / 2].totalcount;
			j++;
		}
		tmpcount.push_back(tmpyull);
		if (tmpyull > maxyull) { maxyull = tmpyull; }
	}
	 yull = maxyull;
	 for (int i = 0; i < tmpcount.size(); i++) { //나머지 부분 0으로 채우기
		 for (int j = yull - 1; j >= 0; j--) {
			 if (tmpcount[i] - 1 < j) {
				 ground[i][j] = 0;
			 }
			 else break;
		 }
	 }
}
void Ccal() {
	int maxhang = 0;
	vector<int> tmpcount;
	for (int i = 0; i < yull; i++) {
		int tmphang = hang;
		vector<xx> xarr;
		for (int j = 0; j < tmphang; j++) {
			if (ground[j][i] == 0) continue;
			bool c = false;
			for (int k = 0; k < xarr.size(); k++) {
				if (ground[j][i] == xarr[k].xnum) {
					xarr[k].totalcount++; c = true; break;
				}
			}
			if (c == false) {
				xarr.push_back({ ground[j][i],1 });
			}
		}
		sort(xarr.begin(), xarr.end(), compare); //정렬
		tmphang = xarr.size() * 2;
		for (int j = 0; j < tmphang; j++) {
			ground[j][i] = xarr[j / 2].xnum;
			ground[j + 1][i] = xarr[j / 2].totalcount;
			j++;
		}
		tmpcount.push_back(tmphang);
		if (tmphang > maxhang) { maxhang = tmphang; }
	}
	hang = maxhang;
	for (int i = 0; i < tmpcount.size(); i++) {
		for (int j = hang - 1; j >= 0; j--) {
			if (tmpcount[i] - 1 < j) {
				ground[j][i] = 0;
			}
			else break;
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int second = 0;
	inputs();
	while (1) {
		if (ground[r-1][c-1] == k) { cout << second << "\n"; return 0; }
		if (second > 100) { cout << -1 << "\n"; return 0; }
		if (hang >= yull) {
			Rcal();
		}
		else {
			Ccal();
		}
		second++;
	}
	return 0;
}