대엉코딩

www.acmicpc.net/problem/10815

1. 풀이방법

- 일단 문제 input사이즈를 보면 크다 500,000

- 만약 두번의 for문을 돌려서 탐색을 할경우 최악의경우 250,000,000,000 인데, 

- c++기준 대략 1초에 1억번의 연산을 한다고 가정하여도, 시간제한 2초를 훨씬 넘기 때문에 

- 선형탐색을 사용해서는 안된다 ----->이진탐색(binary search)를 사용하자.

- 오름차순으로 sorting을 한 후 시작한다.

2.주의사항

- 전형적인 이진탐색문제로서 이론을 그대로 코드로 옮겨주면 되겠다.

- 조건을 살짝씩 빼먹을 경우 무한루프에 자주 빠지니 조건을 꼼꼼하게 체크 해주자....>!

3. 나의코드

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

int N, M;
int Narr[500001];
int Marr[500001];

void inputs() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Narr[i];
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> Marr[i];
	}
}
void bs(int start,int end,int searchnum) {
	int mid = (start + end) / 2;
	if (Narr[mid] == searchnum) { cout << 1 << " "; return; }
	if (mid >= end) { cout << 0 << " "; return; }
	if (Narr[mid] > searchnum) { bs(start, mid-1, searchnum); }
	if (Narr[mid] < searchnum) { bs(mid+1, end, searchnum); }
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	sort(Narr, Narr+N);
	for (int i = 0; i < M; i++) {
		bs(0, N - 1, Marr[i]);
	}
	return 0;
}

www.acmicpc.net/problem/17135

1.풀이방법

- 3명의 궁수가 (N,0) (N,M-1)까지 배치될 수 있는 모든 CASE를 생성하여 게임을 시작합니다. (조합)

- 격자에서 모든 적이 사라지면 게임을 종료

- 3명의 궁수를 대상으로 모든 적들의 거리를  계산후 좌표와 거리를 구조체로 선언하여, eset(enemy set)에 넣고

- sort를 진행(거리가 가까운 순, 같으면 좌표 y가 더 작은 순(왼쪽))

2. 주의사항

- 조합만 잘 구현하면 문제는 조건대로 찬찬히 구현하면 해결 완료.

3.나의코드

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

int ground[17][17];
int copyground[17][17];
bool selected[17];
vector<pair<int, int>> archer;
int maxresult = -1;
int N, M;
int D;
int enemycount;
struct enemy { int x; int y; int d; };

bool cmp(enemy a, enemy b) {
	if (a.d < b.d) { return true; }
	else {
		if (a.d == b.d) {
			if (a.y < b.y) { return true; }
			else { return false; }
		}
		return false;
	}
}

void inputs() {
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> ground[i][j];
			copyground[i][j] = ground[i][j];
		}
	}
}
void groundinit() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			ground[i][j] = copyground[i][j];
		}
	}
}
bool checkground() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (ground[i][j] == 1) { return false; }
		}
	}
	return true;
}
int abs(int n1, int n2) {
	if (n1 > n2) { return n1 - n2; }
	else return n2 - n1;
}
int getdistance(int x, int y, int x2, int y2) {
	return (abs(x, x2) + abs(y, y2));
};
void enemymove() {
	for (int i = N - 1; i >= 0; i--) {
		for (int j = 0; j < M; j++) {
			if (ground[i][j] == 1) {
				ground[i + 1][j] = 1; ground[i][j] = 0;
			}
		}
	}
}
void startgame() {
	while (1) {// 반복한번 = 1턴
		if (checkground() == true) { 
			if (maxresult < enemycount) { maxresult = enemycount; }
			return;
		}
		vector<enemy> eset[3];
		for (int i = 0; i < archer.size(); i++) {
			for (int a = 0; a < N; a++) {
				for (int b = 0; b < M; b++) {
					if (ground[a][b] == 1) {
						if (getdistance(archer[i].first, archer[i].second, a, b) <= D) {
							enemy tmp; tmp.x = a; tmp.y = b; tmp.d = getdistance(archer[i].first, archer[i].second, a, b);
							eset[i].push_back(tmp); //1명의 궁수당 적이 들어있음 거리와 함께
						}
					}
				}
			}
			sort(eset[i].begin(), eset[i].end(), cmp);
		}
		//각각의 궁수에 대해서 0번쨰 인덱스의 적이 죽을 차례
		for (int i = 0; i < archer.size(); i++) {
			if (eset[i].empty() == true) continue; //사정거리내의 적이 없음
			if (ground[eset[i][0].x][eset[i][0].y] == 1) {
				ground[eset[i][0].x][eset[i][0].y] = 0; //적을 없앤다
				enemycount++;
			}
		}
		enemymove();
	}
}


void makecase(int index,int num) {
	if (num == 3) {
		enemycount = 0;
		groundinit();
		startgame(); return;
	}
	pair<int, int> tmp;
	tmp.first = N;
	for (int i = index; i < M; i++) {
		if (selected[i] == true  ) continue;
		tmp.second = i;
		archer.push_back(tmp);
		selected[i] = true;
		makecase(i,num + 1);
		archer.pop_back();
		selected[i] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	inputs();
	makecase(0,0);
	cout << maxresult;

	return 0;
}

www.acmicpc.net/problem/14890

1. 풀이방법.

- 말 그대로 그냥 문제 조건을 구현해야 하는데...

- 처음엔 왼쪽으로 쭉한번보고 오른쪽으로 쭉한번보고 위아래도 마찬가지로 하면된다 생각했었는데

- 223322 [L=2] 같은 경우가 안되는 것을 보고 접근 방식을 바꿨습니다.

-높이가 1차이 나는 친구를 만날경우 나보다 큰 친구면 나부터 뒤쪽을 보고

- 나보다 작은 친구면 나의 앞쪽부터 L만큼을 살펴 보았습니다.

2. 주의사항

- 나보다 큰 친구, 작은친구 의 분류로 나눠서 확인할 때, 저는 현재 위치를 INIT 앞쪽 친구를 loadmap[i][j]로 두었기 때문

- 에 비교문에서 값에 신경을 써야했습니다.

- 문제에 다양한 예시입력이 있어서 다행이었습니다.....아니였으면 꽤 오래 답을 찾아야 했을 것 같습니다.

- 후....문제에 대한 아이디어가 생각나면 그 아이디어로 해결이 될 것만 같은 [즉, 예외되는 사항이 발생하는 경우 를 잘

-떠올리지 못하는 것 같습니다]

- 코드를 작성하기 전에 한번 더 생각해보고 천천히 접근하자.....!

3. 나의코드

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

int N;
int loadmap[101][101];
int L;
int result = 0;
int init;
bool check;
bool checkrow[101];

void inputs() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> loadmap[i][j];
		}
	}
}
int gap(int a, int b) {
	if (a > b) return a - b;
	else { return b - a; }
}
void initcheck() {
	for (int i = 0; i < 101; i++) {
		checkrow[i] = 0;
	}
}
void lookr() {
	for (int i = 0; i < N; i++) {
		initcheck();
		init = loadmap[i][0];
		check = true;
		for (int j = 1; j < N; j++) {
			if (init == loadmap[i][j]) { init = loadmap[i][j]; continue; }
			if (gap(init, loadmap[i][j]) == 1) { //높이1차이
				if (init < loadmap[i][j]) { //벽을 만남(나보다 큰)
					if (j - L < 0) { check = false; break; }
					else {
						for (int k = 1; k <= L; k++) {
							if(checkrow[j-k]==true || loadmap[i][j - k] != init)
							 { check = false; break; }
						}
						for (int k = 1; k <= L; k++) {
							checkrow[j - k] = true;
						}
						if (check == false) break;
					}
				}
				else { //나보다 작은 친구를 만남
					if(j+L>N) { check = false; break; }
					else{
						for (int k = 0; k < L; k++) {
							if (checkrow[j+k]==true||loadmap[i][j + k] != init-1)
							{ check = false; break; }
						}
						for (int k = 0; k < L; k++) {
							checkrow[j + k] = true;
						}
						if (check == false) break;
						j += L-1; //앞에다가 경사로를 놓았을 경우 점프가 필요
					}
				}
			}
			else {check = false; break;} //높이1차이 이상
		init = loadmap[i][j];
		}
		if (check == true) { result++;  }
	}
}
void looku() {
	for (int i = 0; i < N; i++) {
		initcheck();
		init = loadmap[0][i];
		check = true;
		for (int j = 1; j < N; j++) {
			if (init == loadmap[j][i]) { init = loadmap[j][i]; continue; }
			if (gap(init, loadmap[j][i]) == 1) { //높이1차이
				if (init < loadmap[j][i]) { //벽을 만남(나보다 큰)
					if (j - L < 0) { check = false; break; }
					else {
						for (int k = 1; k <= L; k++) {
							if (checkrow[j - k] == true || loadmap[j - k][i] != init)
							{
								check = false; break;
							}
						}
						for (int k = 1; k <= L; k++) {
							checkrow[j - k] = true;
						}
						if (check == false) break;
					}
				}
				else { //나보다 작은 친구를 만남
					if (j + L > N) { check = false; break; }
					else {
						for (int k = 0; k < L; k++) {
							if (checkrow[j + k] == true || loadmap[j + k][i] != init - 1)
							{
								check = false; break;
							}
						}
						for (int k = 0; k < L; k++) {
							checkrow[j + k] = true;
						}
						if (check == false) break;
						j += L-1; //앞에다가 경사로를 놓았을 경우 점프가 필요
					}
				}
			}
			else { check = false; break; } //높이1차이 이상
			init = loadmap[j][i];
		}
		if (check == true) { result++;  }
	}
}

void checkingload() {
	lookr();
	looku();
	cout << result;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> L;
	inputs();
	checkingload();
	return 0;
}

www.acmicpc.net/problem/17136

1. 풀이방법

- 하... 이문제 때문에 여간 고생한게 아니다;;

- 정확한 이유는 모르겠는데 처음에 맵을 탐색하다가 1을 발견하면 5가지의 색종이를 모두 붙이는 식으로

- 구현을 했었는데 계속 종료조건이 애매해서 어쩔 줄 몰라 하다가,,,, 탐색을 하는 부분이랑 색종이를 붙여보는

- 것을 나눠서 구현했더니 해결이 되었습니다.

- 자신감이 딱 붙어갈 타이밍에 좌절을 준 문제였습니다.....나중에 다시 풀어도 고생할 듯한....

- 전체적인 구조를 종료조건을 잘 생각해서 짜야할 것 같습니다.... 아이디어는 금방 떠올렸으나..참;;

- 개인적으로 힘든 문제였습니다..

2.주의사항

- 종료조건을 적절히 사용할 수 있게끔 전체적인 구조를 생각하고 짜자.....!

3.나의 코드

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

int map[10][10];
int colorpaperset[6];
int minimumpapaer = 101;
void doattach(int, int, int);

void inputsetting() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 1; i < 6; i++) {
		colorpaperset[i] = 5;
	}
}
bool canattach(int x, int y, int r) {
	if (x + r > 10 || y + r > 10) { return false; }
	for (int i = x; i < x+r; i++) {
		for (int j = y; j < y+r; j++) {
			if (map[i][j] == 0) return false;
		}
	}
	return true;
}
void setmap(int x, int y, int r) {
	for (int i = x; i < x + r; i++) {
		for (int j = y; j < y + r; j++) {
			map[i][j] =0;
		}
	}
}
void unsetmap(int x, int y, int r) {
	for (int i = x; i < x + r; i++) {
		for (int j = y; j < y + r; j++) {
			map[i][j] = 1;
		}
	}
}

void attach(int x, int y, int r) {
	int tmpx, tmpy;
	bool c = false;
	for (int i = x; i < 10; i++) { //1인 부분을 탐색
		for (int j = 0; j < 10; j++) {
			if (map[i][j] == 0) {
				if (i == 9 && j == 9) { minimumpapaer = min(minimumpapaer, r); return; }
				// 재귀를 통해 여기까지 왔다는 것 자체가 이미 1을 다 0으로 바꾸고 도착했다는 것
				continue;}
			tmpx = i; tmpy = j; c = true; break;
		}
		if (c == true) break;
	}
	doattach(tmpx, tmpy, r);
}
void doattach(int x, int y, int r) {//붙이기를 시도한다.
	for (int k = 5; k > 0; k--) {
		if (canattach(x, y, k) == true && colorpaperset[k] > 0) {
			setmap(x, y, k);
			colorpaperset[k]--;
			attach(x, y, r + 1); //재귀를 통해 다시 탐색을 수행
			colorpaperset[k]++; //다른 종이에 대해서도 수행을 해봐야하므로
			unsetmap(x, y, k); //원상 복구
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputsetting();
	attach(0, 0, 0);
	if (minimumpapaer == 101) { cout << -1; }
	else { cout << minimumpapaer; }
	return 0;
}

www.acmicpc.net/problem/17471

1.풀이 방법.

- 분류는 dfs로 하였다. (dfs를 통해서 연결된 같은 선거구를 탐색하였고)

- 선거구 1의 첫번째 구역을 기준으로 dfs를 한번 돌리고 , 선거구2의 첫번째 구역을 기준으로 dfs를 한번 수행했다.

- 그랬을때 방문을 체크하는 배열 check의 각 구역은 모두 true로 되어있어야 각 선거구가 모두 연결되어 있다는

뜻이다. (전 그렇게 체크하였습니다.)

- 처음에 조합을 만들어서(단 수의 제한이 없음 N개의 지역을 모두 선거구 1이 가져가는 것만 거르면 됨)

CASE를 만들어서 계산에 들어갔고 들어가서 선거구 2에 선거구1에 포함되지 않은 구역들을 넣어주어서

- 일단 CASE에 대한 선거구1,선거구2를 나누어 주었고 DFS를 돌려 연결되어있는지 확인후.

- 나누어진 선거구가 각자 모두 연결되어있다는 것이 확인되면 인구수의 합의 차이를 결과벡터에

삽입 해주고 소팅 후 최소값을 출력하였습니다.

2. 주의사항

- 전략을 처음에 세우고 들어갔는데..... 노트와 펜으로 세운 전략은 이랬습니다.

-<노트에 쓴 내용>

1. CASE를 만들자(분류) 

2. DFS로 각 CASE가 유효한 CASE인지 확인하자(모두 각자 연결되어 있는지)

3. 인구수 차이를 측정

- 이렇게 세우고 코드를 작성하러 들어갔는데

- 순차적으로 짜다보니 코드가 매우 길어졌습니다.

- 그리고 전역변수에 대한 각 작업 수행시 초기화가 필요한 경우 추가로 함수를 작성하고 하다보니..

  더 길어졌는데.....전략 뿐만아니라 조금 더 명확한 틀을 설정하려고 노력해야겠습니다.....

(코드가 길어지면 짜다 보면 막 헷갈리는 부분이 생기고 갑자기 멍해지기도 하고....;;)

3.나의코드

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

bool check[11]; //방문한 노드인지 확인
int groupindex[11]; //CASE별 각 구역이 어떤 선거구에 포함되어있는지 확인
vector<int> edges[11]; //연결된 간선 정보 저장
int peoplecount[11]; //각 구역별 인구수 저장변수
int tmp;
int N;
vector<int> votecamp1; //선거구1에 해당하는 구역을 담을 벡터
vector<int> resultmin;//각 CASE별 인구 수 차이를 담아놓을 변수

void input() {//입력받는 함수
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> peoplecount[i];
	}
	for (int i = 1; i <= N; i++) {
		cin >> tmp;
		for (int j = 0; j < tmp; j++) {
			int n; cin >> n;
			edges[i].push_back(n);
		}
	}

}
int getsum(vector<int> arr) { //인구수 합 구하는 함수
	int s = 0;
	for (int i = 0; i < arr.size(); i++) {
		s += peoplecount[arr[i]];
	}
	return s;
}
void resetcheck() { //초기화함수
	for (int i = 0; i < 11; i++) {
		check[i] = false;
	}
}
int gap(int num1, int num2) { //단순히 차이를 리턴하는 함수
	if (num1 > num2) { return (num1 - num2); }
	else { return (num2 - num1); }
}
void dfs(int index,int g) { //DFS수행
	check[index] = true;
	for (int i = 0; i < edges[index].size(); i++) {
		if (check[edges[index][i]]==false&&groupindex[edges[index][i]] == g) {
			//방문하지 않았고, 나와 같은 선거구 인 경우 탐색을 수행
			dfs(edges[index][i],g);
		}
	}
	return;
}
bool all() { //모두 방문했는지 체크를 위한 함수
	for (int i = 1; i <= N;i++) {
		if (check[i] == false) return false;
	}
	return true;
}
void groupindexreset() { //초기화 함수
	for (int i = 0; i < 11; i++) {
		groupindex[i] = 1;
	}
}
void checkvotecamp() {
	if (votecamp1.size() == N) { return; }
	vector<int> votecamp2; //선거구2를 담을 변수
	groupindexreset(); //각 지역이 어떤 선거구에 속했는지를 담을 변수 초기화
	for (int i = 1; i <= N; i++) { //1에 속하지 않은 지역은 2에 넣기
		bool c = false;
		for (int j = 0; j < votecamp1.size(); j++) {
			if (votecamp1[j] == i) { c = true; break; }
		}
		if (c == false) { votecamp2.push_back(i);
		groupindex[i] = 2;
		}
	}
	resetcheck();
	dfs(votecamp1[0],1); //선거구의 지역이 모두 연결되어있는지 체크를 위해 DFS
	dfs(votecamp2[0],2);
	if (all() == true) {
		int first = getsum(votecamp1);
		int second = getsum(votecamp2);
		resultmin.push_back(gap(first, second));
	}

}
void makecase(int num) { //조합CASE(수가 정해지지 않은)
	if (num > N) { return; }
	for (int i = num; i <= N; i++) {
		votecamp1.push_back(i);
		checkvotecamp();
		makecase(i + 1);
		votecamp1.pop_back();
	}
}
int main() {
	// 1 ~ N 의 구역
	input(); //입력
	makecase(1); //케이스 만들자
	sort(resultmin.begin(), resultmin.end()); //최소값 출력 부
	if (resultmin.empty()) { cout << -1; return 0; }
	cout << resultmin[0];
	return 0;
}

www.acmicpc.net/problem/16637

1.풀이방법

- 수식과 정수를 나누는 작업을 따로 하지는 않았고 모두 index를 통해서 접근하였습니다.

- 모든 경우의 수를 재귀를 통해서 구현한 후 연산하시면 됩니다.

- 처음에 문제조건을 파악하고 무조건 dp라고 생각하고 반복문을 이용해서 바텀업 방식으로 구현을 했는데

- 계속 틀렸다고 나와서 방식을 약간 바꿨는데......하 아직도 첫 소스에서는 어떤 사항을 잡지 못하는지

- 모르겠네요...... 역시 테스트케이스는 되는데 제출하면 틀릴 때는 참 예외사항 발견하기가 어렵네요

- 두번째로 틀린 소스도 올릴테니 지적과 조언좀 부탁드려요...(뭐가 잘못 되었을 까요......ㅠ)

2. 주의사항

- 어이가 없지만.......1일 경우 if문을 걸어 그냥 바로 출력하게끔 했는데,,,,, return 0;을 안줘서

- 계쏙 88퍼 쯤에서 틀렸습니다....ㅎ...한참 고민했는데 어이가 없었네요.....기본적인 실수를 줄이도록...해야겠습니다...

3. 나의 코드

<정답 코드>

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


int N;
string inputs;
vector<long long> maxresult;
long long tmpnum;

long long cal(long long num1, long long num2, char c) {
	if (c == '+') { return num1 + num2; }
	else if (c == '-') { return num1 - num2; }
	else {
		return num1 * num2;
	}
}
void dfs(int index, long long nowvalue) {
	if (index >= N - 1) {
		maxresult.push_back(nowvalue);
		return;
	}
	tmpnum = cal(nowvalue, inputs[index + 2] - '0', inputs[index + 1]);
	dfs(index + 2, tmpnum);
	if (index + 4 <= N - 1) {
		long long first = cal(inputs[index + 2] - '0', inputs[index + 4] - '0', inputs[index + 3]);
		tmpnum = cal(nowvalue, first, inputs[index + 1]);
		dfs(index + 4, tmpnum);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	cin >> inputs;
	if (N == 1) { cout << inputs[0] - '0' << "\n"; return 0; }
	dfs(0, inputs[0] - '0');
	sort(maxresult.begin(), maxresult.end());
	cout << maxresult[maxresult.size() - 1] << "\n";
	return 0;
}

<오답 코드>  ---- 지적해주세요 !ㅠㅠ

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

long long dp[20]; // 결과를 저장할 테이블
int N;
string inputs;

long long cal(long long num1, long long num2, char c) {
	if (c == '+') { return num1 + num2; }
	else if (c == '-') { return num1 - num2; }
	else {
		return num1 * num2;
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	cin >> inputs;
	dp[0] = inputs[0] - 48;
	dp[2] = cal(inputs[0] - 48, inputs[2] - 48, inputs[1]);
	if (N == 1) { cout << dp[0] << "\n"; return 0; }
	if (N == 3) {cout << dp[3] << "\n"; return 0;}
	for (int i = 4; i < N; i += 2) {
		long long first = cal(inputs[i - 2] - 48, inputs[i] - 48, inputs[i - 1]);
		first = cal(dp[i - 4], first, inputs[i - 3]);
		long long second = cal(dp[i - 2], inputs[i] - 48, inputs[i - 1]);
		dp[i] = max(first, second);
	}
	cout << dp[N - 1] << "\n";
	return 0;
}

www.acmicpc.net/problem/17406

1. 풀이 방법

- 경우의 수는 명령의 순서에 따라 결과가 달라지므로 순열로 구했습니다.

- 회전을 구현해야 하는데, 바깥쪽 부터 한 겹씩 회전을 시키는 순으로 했고

=

  맨 안쪽에 남은 하나는 오른쪽으로 가려고 하는데 이미 방문한 곳이면 break 하게끔 하였습니다.

-코드가 많이 길어졌네요...ㅠ

2.주의할 점.

- 코드가 길어지다보니 처음 짠 부분에서 이곳 저곳에서 문제가 발생...

   디버깅을 한참했습니다...

-디버깅을 아예 안하기는 쉽지 않겠지만 처음 짤 때 그래도 좀 세심하게 해야겠네요...

-그리고 (r-s,r+s) 입력이 이런식 이기때문에 행과 열의 수는 모두 홀수 입니다.

(처음에 짝수 개도 되는 경우의 수도 생각하고 짰었는데...풀다보니 발견...)

- 조건에 따른 문제를 정확하게 파악해야겠습니다...

3. 나의코드

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

int N, M;
int K,r,s;
int doublearr[51][51]; //본 2차원 배멸 (변화 x)
int caculdoublearr[51][51]; //case별 결과값을 뽑아내기 위한 배열
int copydoublearr[51][51]; //이동을 위해 값을 복사해놓을 임시배열
bool check[51][51];
bool selected[7];
vector<int> resultmin;

struct rcs {
	int r,c,s;
};
vector<rcs> command; //입력받은명령
vector<rcs> casecommand; // 각 경우의수 (시뮬레이션 돌릴)

void input() { // 입력받는 함수		
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> doublearr[i][j];
		}
	}
	rcs tmp;
	for (int i = 0; i < K; i++) {
		cin >> tmp.r >> tmp.c >> tmp.s;
		command.push_back(tmp);
	}
}
void copyarr() { // 원본배열은 그대로 두고 복사해서 사용 (각 테스트케이스마다 써야하므로)
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			copydoublearr[i][j] = doublearr[i][j];
			caculdoublearr[i][j] = doublearr[i][j];
		}
	}
}
void initcheck() { // 방문배열 초기화
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			check[i][j] = false;
		}
	}
}
void copycal() { //한번회전한 배열을 계산을 위한 배열에 복사
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			copydoublearr[i][j] = caculdoublearr[i][j];
		}
	}
}
void turnarr(int r, int c, int s) { //회전을 구현
	int x = r - s;
	int y = c - s;
	int tmpcount = 0;
	int totalcount = 8 * s; //연산해야하는 횟수 한 바퀴에
	char dir = 'R';
	initcheck();
	while (1) {
		if (totalcount == tmpcount) { //바깥한바퀴 -> 안쪽 바퀴로 들어감
			x += 1; y += 1; s -= 1; totalcount = 8 * s;
			tmpcount = 0;
		}
		if (dir == 'R') {
			if (check[x][y+1] == true) { copycal(); break;
			}
			caculdoublearr[x][y + 1] = copydoublearr[x][y];
			tmpcount++;
			check[x][y] = true;
			y += 1;
			if (y == c + s) { dir = 'D'; }
		}
		else if (dir == 'D') {
			caculdoublearr[x + 1][y] = copydoublearr[x][y];
			tmpcount++;
			check[x][y] = true;
			x += 1;
			if (x == r + s) { dir = 'L'; }
		}
		else if (dir == 'L') {
			caculdoublearr[x][y - 1] = copydoublearr[x][y];
			tmpcount++;
			check[x][y] = true;
			y -= 1;
			if (y == c - s) { dir = 'U'; }
		}
		else {
			caculdoublearr[x - 1][y] = copydoublearr[x][y];
			tmpcount++;
			check[x][y] = true;
			x -= 1;
			if (x == r - s) { dir = 'R'; }
		}
	}
}
int getmin() { //배열의 최소값을 뽑아내는 함수
	int mini = 5001;
	for (int i = 1; i <= N; i++) {
		int tmpsum = 0;
		for (int j = 1; j <= M; j++) {
			tmpsum += caculdoublearr[i][j];
		}
		if (tmpsum < mini) { mini = tmpsum; }
	}
	return mini;
}
void relocating() { //명령을 수행 (회전명령)
	copyarr();
	for (int i = 0; i < K; i++) {
		turnarr(casecommand[i].r, casecommand[i].c, casecommand[i].s);
	}
	resultmin.push_back(getmin());
}
void simulation(int n) { //순열 경우의 수 생성
	if (n == K) {
		relocating(); 
		return;
	}
	for (int i = 0; i < command.size(); i++) {
		if (selected[i] == true) continue;
		selected[i] = true;
		casecommand.push_back(command[i]);
		simulation(n+1);
		casecommand.pop_back();
		selected[i] = false;
	}
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	input();
	simulation(0);
	sort(resultmin.begin(), resultmin.end());
	cout << resultmin[0];
	return 0;
}

www.acmicpc.net/problem/18352

1. 풀이방법

- 일단 N의 개수가 300,000이므로 굉장히 큽니다.

- 이차원배열을 고정으로 선언할 경우 작동이 안됩니다.

- 따라서 vector를 이용하여 vector[x].push_back(y) --> x에서가는 y에대해 가는 간선이 있다는 정보저장

- 조건 중 중요한것은 간선의 가중치가 모두 1이라는 것....!  --->이게 있으므로 bfs를 수행하여 최단거리를 구할 수 있다  고 생각 할 수 있습니다.

- 최단거리로 가는 도시들만 출력해야 하므로 visited 배열을 통해 방문한 노드인지 체크를 하며 bfs를 수행하면 됩니다.

- 큐를 이용했고 거리만큼의 bfs를 수행한 후에는 벡터에 옴겨 sorting을 해서 차례로 출력하여 주었습니다.

2. 주의사항

- 조건상에서 왜 bfs를 수행해서 구할 수 있는지 파악 (정당성)

3. 나의 코드

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

queue<int> tmpqueue;
vector<int> edge[300001]; //간선정보저장
bool visited[300001]; //방문정보 저장
int N, M, K, X;
int loadlength;

void inputedge() { //간선정보를 저장
	int x, y;
	for (int i = 0; i < M; i++) {
		cin >> x >> y;
		edge[x].push_back(y);
	}
}

void resultoutput() { //오름차순 정렬 (큐에서 벡터로 옴겨서)
	vector<int> resultsave;
	while (tmpqueue.empty()!=true) {
		resultsave.push_back(tmpqueue.front());
		tmpqueue.pop();
	}
	sort(resultsave.begin(), resultsave.end());
	for (int i = 0; i < resultsave.size(); i++) {
		cout << resultsave[i] << "\n";
	}
}

void bfs(int X) {
	tmpqueue.push(X);
	visited[X] = true;
	while (1) {
		if (tmpqueue.empty()) { cout << -1 << "\n"; break; }
		if (loadlength == K) { resultoutput(); break; }
		int qsize = tmpqueue.size();
		while(qsize--){
			int startnode = tmpqueue.front();
			for (int i = 0; i < edge[startnode].size(); i++) {
				if (visited[edge[startnode][i]] == false) {
					tmpqueue.push(edge[startnode][i]);
					visited[edge[startnode][i]] = true;
				}
			}
			tmpqueue.pop();
		}
		loadlength++;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> K >> X;
	inputedge();
	bfs(X);

	return 0;
}