이것 저것 &

문제링크:https://www.acmicpc.net/problem/5014

버튼의 수의 최솟값을 출력하는 문제로 최단경로값을 구하는 문제였다. 자연스럽게 bfs로 해결할 수 있음을 인지해서 그렇게 풀었다. 

첫번째로 조심해야할 조건은 만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다 이다. 이동할 수 없으면 그자리에서 이동하지 않는다.

첫번째 조건은 문제를 읽고 인지하고 있었기 때문에 문제가 되지 않았는데, 두 번째 예외가 있었다. 출발점과 도착점이 같은경우에는 0을 출력해줘야 하는 문제점이다. 

그래도 틀린다면 한가지 테스트 케이스를 돌려보세요. 10 5 4 0 1 .......

감이 오시나요?? 저는 이 예외를 인지하지 못해서 엄청 고통받았습니다.

아마 틀리셨다면 위 3개의 조건중에 해답이 있을 거라고 생각합니다. 예외처리 이외의 문제 구현은 어려움이 없으셨을 거라고 생각합니다. 

아래는 정답코드입니다.

#include <iostream>
using namespace std;
int f, s, g, u, d;
int que[1000001];
int start=0, ended=0;
int visited[1000001] = { 0 };

void bfs() {

	que[ended++] = s;

	while (start != ended) {

		int current = que[start++];

		if (current + u <= f && !visited[current + u]&& u!=0) {
			visited[current + u] = visited[current] + 1;
			que[ended++] = current + u;
		}
		if (current - d > 0 && !visited[current - d] && d!=0) {
			visited[current - d] = visited[current] + 1;
			que[ended++] = current - d;
		}

	}
}

int main() {
	cin >> f >> s >> g >> u >> d;

	bfs();

	if (!visited[g] && f != s)
		cout << "use the stairs" << endl;
	else
		cout << visited[g] << endl;;
}

문제링크:https://www.acmicpc.net/problem/10026

dfs문제입니다. bfs로도 풀 수 있고 단순히 완전탐색을 하면서 갯수를 세어주면 되는 간단한 문제였습니다. 

방문했는지 여부와 같은색인지를 판별해서 탐색을 했습니다. bfs, dfs 모두 쉽게 구현가능하니까 직접 구현해보시면 좋을 것 같습니다.

너무쉬워서 설명은 생략하겠습니다. 

정답코드입니다. 화이팅 :)

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int n = 0,normal =0,medicine=0;
string arr[100];
bool visited[101][101] = { 0 };
int dex[4] = { 1,-1,0,0 };
int dey[4] = { 0, 0,1,-1 };
void dfs(char color,int x,int y) {

	visited[y][x] = 1;
	
	for (int i = 0; i < 4; i++) {
		int yy = y + dey[i];
		int xx = x + dex[i];
		if (xx >= 0 && xx < n && yy >= 0 && yy< n)
			if (!visited[yy][xx] && arr[yy][xx] == color)
				dfs(color, xx, yy);
	}
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for(int i=0;i<n;i++)
		for (int j = 0; j < arr[i].size(); j++) 
			if (!visited[i][j]) {
				dfs(arr[i][j], j, i);
				normal++;
			}

	memset(visited, 0, sizeof(visited));

	for (int i = 0; i<n; i++)
		for (int j = 0; j < arr[i].size(); j++) 
			if (arr[i][j] == 'R') arr[i][j] = 'G';

	for (int i = 0; i<n; i++)
		for (int j = 0; j < arr[i].size(); j++)
			if (!visited[i][j]) {
				dfs(arr[i][j], j, i);
				medicine++;
			}

	cout << normal << ' '<< medicine << endl;
	
}

문제링크:https://www.acmicpc.net/problem/2668

dfs문제입니다.

N의 범위가 100밖에 안되기 때문에 모든 인자에 대하여 사이클 여부를 확인하는 식으로 진행해도 시간초과가 발생하지 않습니다.

1. 각 인덱스마다 해당 값을 사이클을 가지는지 확인합니다.

        1) 방문여부, start와 current의 위치가 같다면 해당값을 포함합니다.

        2) 방문하지 않았다면 방문을 표시하고, arr[current] 로 이동해서 확인합니다.

2. 사이클을 가진다면 해당값을 result배열에 포함합니다. (이때 인덱스가 작은값부터 포함하기 때문에 정렬할 필요가 없습니다.)

정답코드입니다.

#include <iostream>
#include <cstring>
using namespace std;

int n = 0, result_index = 0;
int arr[101] = { 0 };
int visited[101] = { 0 };
int result[101] = { 0 };

void dfs(int current,int start) {
	if (visited[current]) {
		if (current == start)
			result[result_index++] = start;
	}
	else {
		visited[current] = 1;
		dfs(arr[current], start);
	}

}

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	
	for (int i = 1; i <= n; i++) {
		memset(visited, 0, sizeof(visited));
		dfs(i, i);
	}

	cout << result_index << endl;
	for (int i = 0; i < result_index; i++)
		cout << result[i] << endl;
}

문제링크:https://www.acmicpc.net/problem/2583

전형적인 dfs 문제입니다. (bfs로도 풀이는 가능합니다.)

분리된 공간의 넓이를 출력하면 되는 문제입니다.

위와같이 되어있어서 사각형을 판단하는데 어려움을 가지실 수 있습니다.

하지만 저건 그냥 일반점으로 보아도 무방합니다.

사각형 하나를 그냥 점으로 보세요.

보이시나요?

0~m, 0~n까지입니다. 

해당위치들을 표시해주고 dfs를 통해서 몇번 탐색이 가능한지 확인하고 결과를 도출합니다.

정답코드입니다.

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

int m = 0, n = 0, k =0;
int arr[102][102] = { 0 };
int x, y, x2, y2;

int result[101] = { 0 };
int sum = 0, result_index = 0;
int x_dep[4] = { 1,-1,0,0 };
int y_dep[4] = { 0, 0,-1,1 };

void dfs(int yy, int xx) {
	
	arr[yy][xx] = -1;
	sum++;

	for (int i = 0; i < 4; i++)
	{
		int yyy = yy + y_dep[i];
		int xxx = xx + x_dep[i];

		if (yyy >= 0 && yyy < m && xxx >= 0 && xxx < n) {
			if (arr[yyy][xxx] == 0)
				dfs(yyy, xxx);
		}

	}
	
}
int main() {
	cin >> m >> n >> k;

	for (int i = 0; i < k; i++) {
		cin >> x >> y >> x2 >> y2;

		for (int j = y; j < y2; j++) {
			for (int u = x; u < x2; u++) {
				arr[j][u] = 1;
			}
		}
	}


	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 0) {
				sum = 0;
				dfs(i, j);
				result[result_index++] = sum;
			}
		}
	}

	sort(result, result + result_index);

	cout << result_index << endl;
	for (int i = 0; i < result_index; i++)
		cout << result[i] << " ";
	cout << endl;
}

저는 dfs가 가장 노력하는만큼 실력이 늘어나는 알고리즘이라고 생각합니다. :0

꼭 직접 작성해보세요. 화이팅! 

문제링크: https://www.acmicpc.net/problem/1251

모든 경우의 수를 비교해봐야하는 브루트 포스 문제입니다.

즉, 완전탐색을 하는 것입니다.

비교적 쉬운 난이도였지만, 틀리기 좋았던 부분은 단어를 쪼갤때

1. 삼등분을 해야하기 때문에 중복이 되면 안된다.

2. 세가지 덩어리가 순서대로 돌아와야한다.

오답코드가 있으시다면 해당 테스트케이스를 확인해보세요.

afbdba -> abdbfa

정답코드입니다.

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

string input,result;
string a, b;

int main() {
	cin >> input;

	result = "{"; 

	for (int i = 0; i < input.size()-2; i++) {
		for (int j = i+1; j < input.size()-1; j++) {
			
			string val;

			for (int u = i; u >= 0; u--)
				val += input[u];

			for (int u = j; u > i; u--)
				val += input[u];

			for (int u = input.size() - 1; u > j; u--)
				val += input[u];

			if (result > val) result = val;
			
		}
		
	}


	cout << result << endl;
}

문제링크: https://www.acmicpc.net/problem/1051

브루트포스 문제입니다. 모든 점에서 꼭짓점값들을 확인해서 가장크게 만들 수 있는 정사각형 넓이를 출력하는 문제였습니다. 정답률이 30퍼때라 좀 어려울 줄 알았는데 생각보다 너무 쉬워서 놀랐습니다.

각 점에서 오른쪽과 아래로 내려갈 수 있는 값들을 고려하면서 값을 도출합니다.

코드가 너무 쉬워서 설명은 생략하겠습니다. :)

아래는 정답코드입니다. 

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

int n, m, result = 1;
int arr[51][51] = { 0 };
string input;

int main() {

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
			cin >> input;
			for (int j = 0; j < input.size(); j++)
				arr[i][j] = input[j] - '0';
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int cnt = 0;
			for (int k = 1;; k++) {
				if ((j + k) >= m || (i + k) >= n) break;
				if (arr[i][j] == arr[i][j + k] && arr[i][j] == arr[i + k][j] && arr[i][j] == arr[i + k][j + k])
					if(cnt < k)
						cnt = k;
			}
			if ((cnt + 1) > result) result = cnt + 1;
		}

	}

	cout << result * result << endl;
}

문제링크:https://www.acmicpc.net/problem/2966

전형적인 브루트포스문제였습니다.

어렵지 않았을 것이라고 생각합니다.

너무 쉬운문제라서 설명은 생략하겠습니다.

#include <iostream>
using namespace std;

char a[3] = { 'A','B','C' };
char b[4] = { 'B','A','B','C' };
char c[6] = { 'C','C','A','A','B','B' };
char arr[101];
int cnt[3] = { 0 };

int n = 0, result = 0;

int main() {
	cin >> n;
	cin >> arr;

	for (int i = 0; i < n; i++) {
		if (a[i % 3] == arr[i]) cnt[0]++;
		if (b[i % 4] == arr[i]) cnt[1]++;
		if (c[i % 6] == arr[i]) cnt[2]++;
	}
	for (int i = 0; i < 3; i++)
		if (result < cnt[i]) result = cnt[i];
	cout << result << endl;
	if (cnt[0] == result) cout << "Adrian" << endl;
	if (cnt[1] == result) cout << "Bruno" << endl;
	if (cnt[2] == result) cout << "Goran" << endl;
}

문제링크:https://www.acmicpc.net/problem/2503

모든 경우를 고려해주며 결과값을 도출하는 브루트포스 문제였습니다.

숫자의 범위가 적기 때문에 어려운 점은 없는 문제였습니다.

1) 100~999까지의 수를 반복하며 확인 

2) 이때 0을 포함, 혹은 같은 자릿수를 가지는 수는 제외

3) 같은 자릿수를 가지면 strike값을 올리고 다른 자리에 해당 값이 있다면 ball값을 올려줍니다.

4) 조건을 만족하는 수가 있다면 결과값을 +1씩 올려줍니다.

2번조건을 간과해서 틀릴 수 있습니다. 문제조건을 한번더 확인하는 습관을 가져야겠습니다.

직접문제를 풀어보세요! :0 화이팅

#include <iostream>
#include <algorithm>
using namespace std;
int n = 0, result = 0;
int arr[100][3] = { 0 };
int arr2[9] = { 0 };
int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
	}

	for (int i = 100; i <= 999; i++) {
		if (i % 10 == 0) continue; //0 안들어가게
		if ((i / 10) % 10 == 0) continue;

		if (i / 100 == (i / 10) % 10) continue;
		if (i / 100 == i % 10) continue;
		if (i % 10 == (i / 10) % 10) continue;
		bool jud = true;

		for (int j = 0; j < n; j++) {
			for (int k = 1; k <= 9; k++) arr2[k] = 0;
			bool first = false, second = false, third = false;

			int strike = 0, ball = 0;
			int num = i;
			
			if (num / 100 == arr[j][0] / 100) strike++,first=true;
			arr2[arr[j][0] / 100]++;

			if ((num / 10) %10 == (arr[j][0] / 10)%10) strike++,second=true;
			arr2[(arr[j][0] / 10) % 10]++;

			if (num % 10 == arr[j][0] % 10) strike++,third=true;
			arr2[arr[j][0] % 10]++;
			
			if (!first&&arr2[num / 100]) ball++;
			if (!second&&arr2[(num / 10) % 10]) ball++;
			if (!third&&arr2[num % 10]) ball++;

			if (strike != arr[j][1] || ball != arr[j][2]) {
				jud = false;
				break;
			}

		}
		if (jud == true) {
			
			result++;
		}
	}
	cout << result << endl;
	return 0;
}