대엉코딩

www.acmicpc.net/problem/2644

1. 풀이방법

- 촌수를 계산하는 문제입니다 (두 정점 사이에)

- dfs를 통해서 계산을 하였고 간선의 가중치 (촌수가 1씩 증가)가 1이므로 bfs로도 쉽게 표현 가능할 것으로 보입니다.

- 두 정점이 인접했는지를 확인하는 연산이 주로 쓰이므로 인접행렬방식으로 그래프를 구현하였습니다.

2. 주의사항

- 딱히없음, 특별한 조건도 없고..

3. 나의코드

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

int n, m;
int target1, target2;
bool connected[101][101];
bool visited[101];
bool suc;

void inputs() {
	cin >> n >> target1 >> target2;
	cin >> m;
	int tmp1, tmp2;
	for (int i = 0; i < m; i++) {
		cin >> tmp1 >> tmp2;
		connected[tmp1][tmp2] = true;
		connected[tmp2][tmp1] = true;
	}
}

void findchon(int t,int cnt) {
	visited[t] = true;
	if (t == target2) { cout << cnt << "\n";
	suc = true; return;
	}
	for (int i = 1; i <= n; i++) {
		if (i != t) {
			if (connected[t][i] && !visited[i]) {
				findchon(i, cnt + 1);
			}
			if (suc) break;
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	findchon(target1,0);
	if (suc == false) cout << -1 << "\n";

	return 0;
}

www.acmicpc.net/problem/7569

1. 풀이방법.

- 3차원배열을 이용한 bfs로 해결하였습니다.

- 처음에 input을 받을 때 전체토마토 수, 익은토마토 수를 체크한 후

- bfs를 돌면서 익을 때 마다 익은토마토수를 ++ 해주며,

- 큐가 비었을 때(종료조건) -> 익은토마토수 == 전체토마토수 이면 걸린시간을 출력

                                   -> 익은토마토수 != 전체토마토수 이면 (모두익힐 수 없음 -1출력)

2. 주의사항

- 3차원배열이므로 행,렬,높이 를 스스로 잘 설정하여 H,N,M 과 비교연산 등을 할 때 헷갈리지 않게 주의.

3. 나의코드

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

int tomatobox[101][101][101];//높이,세로행,가로행
bool visit[101][101][101];
int N, M, H;
int totaltomato;
int dx[6] = { 1,-1,0,0,0,0 }; //6방향탐색
int dy[6] = { 0,0,1,-1,0,0 };
int dz[6] = { 0,0,0,0,1,-1 };
struct tomato {
	int h, n, m;
};
queue<tomato> tmpq;
int timecount;
int tomatocount;

void inputs() {
	cin >> M >> N >> H;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				cin >> tomatobox[i][j][k];
				if (tomatobox[i][j][k] == 1) { //익은토마토
					totaltomato++;
					tomatocount++;
					tomatobox[i][j][k] = true;
					tmpq.push({ i,j,k });
				}
				if (tomatobox[i][j][k] == 0) { //익지않은 토마토
					totaltomato++;
				}
			}
		}
	}
}
bool sidecheck(int x, int y, int z) { //경계선 체크
	if (x >= 0 && x < H &&y >= 0 && y < N &&z >= 0 && z < M) return true;
	else return false;
}
void bfs() {
	while (1) {
		int qsize = tmpq.size();
		while (qsize--) {
			tomato thistomato = tmpq.front();
			tmpq.pop();
			for (int i = 0; i < 6; i++) {
				if (sidecheck(thistomato.h+dx[i], thistomato.n+dy[i], thistomato.m+dz[i])
					&&tomatobox[thistomato.h + dx[i]][thistomato.n + dy[i]][thistomato.m + dz[i]]==0 && visit[thistomato.h + dx[i]][thistomato.n + dy[i]][thistomato.m + dz[i]] == false) {
					visit[thistomato.h + dx[i]][thistomato.n + dy[i]][thistomato.m + dz[i]] = true;
					tomatocount++; //토마토가 익음
					tmpq.push({ thistomato.h + dx[i],thistomato.n + dy[i],thistomato.m + dz[i] });
				}
			}
		}
		if (tmpq.empty()) { //종료조건
			if (totaltomato == tomatocount) {
				cout << timecount << "\n";
				return;
			}
			else {
				cout << -1 << "\n";
				return;
			}
		}
		timecount++;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	bfs();

	return 0;
}

www.acmicpc.net/problem/1697

1. 풀이방법.

- 0<N==K<100000 이 되는 모든 경우의 수를 탐색해야합니다.

- 움직일 수 있는 경우의 수는 3가지 X+1,X-1,2*N

- DFS로 모든 경우의수를 탐색할경우 +1,-1씩 이동하는경우 때문에 스택오버플로우가 발생할 것 이라 판단했습니다.

- 그래서 큐를 이용하여 BFS로 해결하였습니다. 

- 딱히 다른 조건도 없어 기본적인 문제였습니다.

2. 주의사항

- 문제 조건 해석 및 판단.

3.나의코드

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

int N, K;
int resultsecond;
bool visit[100001]; //방문체크
queue<int> tmpq;


void bfs() {
	while (1) {
		int qsize = tmpq.size();
		while (qsize--) {
			int thisvalue = tmpq.front();
			tmpq.pop();

			if (thisvalue == K) { //종료조건
				cout << resultsecond << "\n";  return;
			}

			if (thisvalue - 1 >= 0 && visit[thisvalue-1] == false) {
				visit[thisvalue - 1] = true;
				tmpq.push(thisvalue - 1);
			}
			if (thisvalue + 1 <= 100000 && visit[thisvalue+1] == false) {
				visit[thisvalue + 1] = true;
				tmpq.push(thisvalue + 1);
			}
			if (2 * thisvalue <= 100000 && visit[2*thisvalue] == false) {
				visit[2 * thisvalue] = true;
				tmpq.push(2 * thisvalue);
			}
		}
		resultsecond++;
	}
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> K;
	tmpq.push(N);
	visit[N] = true;
	bfs();

	return 0;
}

www.acmicpc.net/problem/16397

1. 풀이방법

- 처음에는 재귀를 이용한 DFS로 모든 경우를 탐색하려고 생각하고 코드를 구상했으나,

- 문제 조건을 보시면 T가 최대 99,999이고, A버튼만 누를 경우 숫자가 1씩 증가하는데 N이 0일경우를 생각해보면

- 재귀를 이용해서 짰을때 stackoverflow를 만났습니다. (조건을 보고 미리 생각했어야되는데....으휴 덤벙덤벙)

- 원리는 비슷한데 queue를 이용해서 bfs로 똑같이 옮겨서 해결했습니다.

2. 주의사항

- 조건도 꼼꼼히 파악하자.

3. 나의코드

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

int N, T, G;
bool visit[100000];
queue<pair<int,int>> tmpq;



int getmodnum(int tmp) {
	int maxmod = 1;
	while (1) {
		if (tmp == 0) break;
		tmp /= 10;
		maxmod *= 10;
	}
	maxmod /= 10;
	return maxmod;
}

int bfs() {
	while (!tmpq.empty()) {
		int tmpn = tmpq.front().first;
		int tmpcnt = tmpq.front().second;
		tmpq.pop();
		if (tmpcnt > T) break;
		if (tmpn == G) return tmpcnt;

		int num = tmpn + 1;
		if (num < 100000 && visit[num] == false) {
			visit[num] = true;
			tmpq.push({ num,tmpcnt + 1 });
		}

		num = tmpn * 2;
		if (num < 100000) {
			int minusnum = getmodnum(num);
			num -= minusnum;
			if (num < 100000 && visit[num] == false) {
				visit[num] = true;
				tmpq.push({ num,tmpcnt + 1 });
			}
		}
	}
	return -1;
}

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

	cin >> N >> T >> G;
	tmpq.push({N, 0}); //시작점
	visit[N] = true;
	int result = bfs();
	if (result == -1) cout << "ANG" << "\n";
	else cout << result << "\n";
	return 0;
}

www.acmicpc.net/problem/13458

1. 풀이방법

- 그냥 구현 문제입니다.

- "오직" 이라는 말이 약간 헷갈린다는 정도? 결국 모든 시험장에 총감독관은 1명 있어야 한다는 말입니다.

2. 주의사항

- 시험장이 최대 1,000,000 개 시험장당 응시자가 최대 1,000,000 입니다.

- 총,부 감독관 모두 1명씩만 감시가능 하다고 생각하면 1,000,000,000,000명이 필요할 수 있습니다.

- INT형으로는 부족 long long 자료형을 사용했습니다.

3. 나의코드

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

int N;
int B, C;
long long resultcount = 0;

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

	cin >> N;
	vector<int> examarea(N);
	for (int i = 0; i < N; i++) cin>>examarea[i];
	cin >> B >> C;

		for (int i = 0; i < N; i++) {
			resultcount++;
			examarea[i] -= B;
			if (examarea[i] <= 0) continue; //총 감독관 혼자 감시 가능
			else { 
				if (examarea[i] % C == 0) resultcount += (examarea[i] / C);
				else resultcount += ((examarea[i] / C) + 1); }
		}

	cout << resultcount << "\n";
	return 0;
}

www.acmicpc.net/problem/6593

1. 풀이방법

- 3차원배열을 이용해야할 뿐 기초적인 BFS 문제입니다

- 범위검사와 BFS, 그리고 E에 도달하지 못했는데 큐가 비어있다면 더이상 갈 곳이 없는 것이므로

- 종료조건을 출력하고 나가면 됩니다.

2. 주의사항

- 구현에 몰두해서 짜다보니 메모리 초과가 떴는데 왜 그런가 봤더니 방문체크를 큐에서 꺼낼 때 하고 있었습니다.

- 그럴경우, 여러정점에서 동시방문하고자 할 수 있기 때문에 문제가 발생할 수 있습니다.

- BFS를 구현할 때는 방문체크를 큐에 넣을 떄 해줍시다.

3.나의코드

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

int L, R, C;
int seconds;
char sangbumbuilding[31][31][31];
bool visit[31][31][31];
int dx[6] = { 1,-1,0,0,0,0 }; //6방향 탐색
int dy[6] = { 0,0,1,-1,0,0 };
int dz[6] = { 0,0,0,0,1,-1 };
struct area {
	int x, y, z;
};

queue<area> tmpq;
area S;
area E;
area tmpa, tmparea;
bool inputs() {
	cin >> L >> R >> C;
	if (L == 0 && R == 0 && C == 0) return true;

	for (int i = 1; i <= L; i++) {
		for (int j = 1; j <= R; j++) {
			for (int k = 1; k <= C; k++) {
				visit[i][j][k] = false;
				cin >> sangbumbuilding[i][j][k];
				if(sangbumbuilding[i][j][k]=='S'){
					S.x = i; S.y = j; S.z = k;
				}
				if (sangbumbuilding[i][j][k] == 'E') {
					E.x = i; E.y = j; E.z = k;
				}
			}
		}
	}
	return false;
}

void bfs(area s) {
	tmpq.push(s);
	while (1) {
		if (tmpq.empty()) { cout << "Trapped!" << "\n"; return; }
		int tmpsize = tmpq.size();
		while(tmpsize--) { //1초당
			tmpa = tmpq.front();
			tmpq.pop();
			if (tmpa.x == E.x &&tmpa.y == E.y&&tmpa.z == E.z) {
				cout << "Escaped in "<<seconds<<" minute(s)."<<"\n"; return;
			}
			for (int i = 0; i < 6; i++) { //6방향탐색
				//범위 검사
				if (tmpa.x + dx[i] >= 1 && tmpa.x + dx[i] <= L && tmpa.y + dy[i] >= 1 && tmpa.y + dy[i] <= R && tmpa.z + dz[i] >= 1 && tmpa.z + dz[i] <= C) {
					if (sangbumbuilding[tmpa.x + dx[i]][tmpa.y + dy[i]][tmpa.z + dz[i]] == '.'|| sangbumbuilding[tmpa.x + dx[i]][tmpa.y + dy[i]][tmpa.z + dz[i]] == 'E') {
						if (visit[tmpa.x + dx[i]][tmpa.y + dy[i]][tmpa.z + dz[i]] == false) {
							tmparea.x = tmpa.x + dx[i]; tmparea.y = tmpa.y + dy[i]; tmparea.z = tmpa.z + dz[i];
							visit[tmparea.x][tmparea.y][tmparea.z] = true;
							tmpq.push(tmparea);
						}
					}
				}
			}
		}
		seconds++;
	}
}
void resetqueue() {
	while (1) {
		if (tmpq.empty()) return;
		tmpq.pop();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	while (1) {
		resetqueue();
		if(inputs()) break;
		seconds = 0;
		bfs(S);
	}
	return 0;
}

www.acmicpc.net/problem/1463

1. 풀이방법

- 맨 처음에는 3으로 나누어떨어지면 -> 2로 나누어떨어지면 -> 이것마저 안되면 -1 이라고 생각했었는데

- 이럴경우 10->5->4->2->1  (답은 10->9->3->1)

- 그리고 나서 숫자를 쭉 써놓고 한번생각을 해보았는데

- 결국 비교해야 할 경우는 3가지 이다 N-1 과 N/3 과 N/2 이다.

- 중요한 것은 경우에 따라 N-1을 한 경우가 최소연산 일 수 있다는 것.

2. 주의사항

- 처음에는 항상 익숙한대로 탑다운 방식(재귀함수)를 이용했다.

-결과는 "메모리 초과"

- 문제 조건을 보았는데 메모리는 128MB까지 허용이 가능하고

- 내가 사용한 용량을 얼추 계산해봐도 1,000,000 * 4바이트(INT) 기껏해서 4MB 정도이다. (짜잘한 것은 생략.)

- 추측한 것은 재귀로 너무 깊이 들어가서 스택메모리가 초과되었나? 라는 생각

- 그래서 재귀를 사용하지 않고 바텀업 방식(반복문이용) 으로 짰더니 통과가 되었습니다.

3. 나의코드

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

int X;
int dp[1000001];

//메모리 초과
/*int getdp(int num) {
	if (dp[num] == 0) {
		if (num % 3 == 0) { dp[num] = min((getdp(num - 1) + 1), (getdp(num / 3) + 1)); return dp[num]; }
		else if (num % 2 == 0) { dp[num] = min((getdp(num - 1) + 1),(getdp(num / 2) + 1)); return dp[num]; }
		else { dp[num] = getdp(num - 1) + 1; return dp[num]; }
	}
	else { return dp[num]; }
}*/
void bottomup() {
	for (int i = 6; i < 1000001; i++) {
		if (i % 3 == 0) {dp[i] = min(dp[i - 1] + 1, dp[i / 3] + 1);}
		else if(i%2==0){ dp[i] = min(dp[i - 1] + 1, dp[i / 2] + 1); }
		else { dp[i] = dp[i - 1] + 1; }
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> X;   //  X>1
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 2;
	dp[5] = 3;
	bottomup();
	cout<<dp[X]<<"\n";
	return 0;
}

www.acmicpc.net/problem/1107

1. 풀이방법

- 개인적으로 참 어려웠던 문제였습니다...

- 처음에는 경우의 수를 나눠서 1번 (+,-만으로만 접근) 2번 (버튼만으로 접근이 가능한 경우) 3번 (버튼으로 근접하게 간 후 +,- 로 이동해야하는 경우) 3가지 중 min 값을 출력하자 라고 했습니다.

- 하지만 저 3번....! 저걸 찾아내는게 굉장히 까다로웠습니다. 숫자를 하나씩 맞춰본다거나, 

  고장난 버튼이면 최대한 근접한 버튼을 누르는데 위,아래 어느 숫자쪽으로 탐색을 해야하나....

- 하나의 아이디어를 준 것은 바로 +,-는 마지막에 눌러진다는 것입니다. +,- 버튼을 누르고 나서 숫자를 누를경우 

  처음 부터 다시 숫자를 매겨야 하죠 (보통의 리모컨을 생각해 보시면 될 것 같습니다.)

- 그래서 생각해낸 것은 바로.....!

- 1. 일단 -1로 모든번호를 저장할 테이블들을 모두 초기화 ! (위로 갔다가 -로 돌아오는 경우도 있으므로 백만까지)

- 2. 버튼으로 이동할 수 있는 번호의 경우 테이블에 미리 다 몇번의 버튼을 눌러서 갈 수 있는지 저장!!!!

- 3. 찾고자 하는 채널이 -1, 즉 버튼만으로 갈 수 없는 경우 위,아래로 탐색해서 가장 가까이 있는 버튼으로 갈 수 있는

      번호를 찾는다 !!!!!!

( 물론 상기의 과정 중 +,- 버튼만으로 가는 것이 더 적은 수로 이동할 수 있는 경우 그 숫자를 넣어줘야 합니다.)

2. 주의사항

- 리모콘은 고장나면 쫌 사자.....

3. 나의코드

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

int N,M;
int remote[10]; //0~9
int casestore[1000001];
int len;

bool onlynum(int num) {
	len = 0;
	int tmp = num;
	while (1) {
		if (remote[tmp % 10] == true) return false; //고장나서 버튼만으로는 이동불가
		tmp /= 10;
		len++;
		if (tmp == 0) break;
	}
	return true;
}
void inputs() {
	cin >> N >> M;
	int tmp;
	for (int i = 0; i < M; i++) {
		cin >> tmp;
		remote[tmp] = true; //true는 고장
	}
}
void makecase() {
	casestore[100] = 0;
	for (int i = 0; i < 1000001; i++) {
		if (i == 100) continue;
		if(onlynum(i)==true)
		{
			casestore[i] = min(abs(i - 100), len);
		}
	}
}
void setcase() {
	for (int i = 0; i < 1000001; i++) {
		casestore[i] = -1;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	setcase();
	makecase();

	if (N == 100) { cout << 0 << "\n"; return 0; }
	if(casestore[N]!=-1){
		cout << casestore[N] << "\n"; return 0;
	}
	else{
		int index = 1;
		while (1) {
			if (N - index >= 0) {
				if (casestore[N - index] != -1) {
					cout << min(abs(N - 100),casestore[N - index] + index) << "\n";
					return 0;
				}
			}
			if (N + index <= 1000000) {
				if (casestore[N + index] != -1) {
					cout << min(abs(N - 100),casestore[N + index] + index) << "\n";
					return 0;
				}
			}
			index++;
		}
	}
	return 0;
}