굳건하게

문제 : https://www.acmicpc.net/problem/5427

[알고리즘풀이]

BFS를 이용하는 전형적인 문제다.

사람은 불이 없더라도, 이제 불이 옮겨붙으려는 칸으로도 이동할 수 없다.

따라서, 먼저 불을 다 이동시키고, 남는 자리에 한해서 사람이 이동하면 된다.

사람이 밖으로 탈출하면 성공한 것이므로 check 함수를 통해

사람이 다음에 이동할 곳 중 밖으로 나가는 곳이 있으면 이동 횟수를 출력하고 종료해주면 된다.

#include<iostream>
#include<string>
#include<queue>
#include<vector>

using namespace std;

char map[1000][1000] = {};
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int t, r, c;

bool check(int x, int y) {
	if (0 <= x && x < r && 0 <= y && y < c)
		return true;
	return false;
}

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

	cin >> t;
	while (t--) {
		cin >> c >> r;
		for (int i = 0; i < r; i++)
			cin >> map[i];

		bool ch = false; // IMPOSSIBLE인지 아닌지 체크
		bool visited[1000][1000] = {}; // BFS 경로
		queue<pair<int, int>> fire;
		queue<pair<pair<int, int>, int>> q;
		for(int i = 0; i < r; i++)
			for (int j = 0; j < c; j++) {
				if (map[i][j] == '*')
					fire.push(make_pair(i, j));
				if (map[i][j] == '@'){
					q.push(make_pair(make_pair(i, j), 0));
					visited[i][j] = true;
				}
			}

		while (!q.empty()) {
			// 불부터 옮기자.
			int sx, sy;
			int end = fire.size();
			for (int i = 0; i < end; i++) {
				pair<int, int> fire_s = fire.front();
				fire.pop();
				for (int j = 0; j < 4; j++) {
					sx = dx[j] + fire_s.first;
					sy = dy[j] + fire_s.second;
					if (check(sx, sy) && map[sx][sy] == '.') {
						map[sx][sy] = '*';
						fire.push(make_pair(sx, sy));
					}
				}
			}
			// 사람을 이동하자.
			end = q.size();
			for (int i = 0; i < end; i++) {
				pair<pair<int, int>, int> s = q.front();
				q.pop();		
				for (int j = 0; j < 4; j++) {
					sx = dx[j] + s.first.first;
					sy = dy[j] + s.first.second;
					if (!check(sx, sy)) {
						cout << s.second + 1 << '\n';
						ch = true;
						break;
					}
					if (map[sx][sy] == '.' && visited[sx][sy] == false) {
						q.push(make_pair(make_pair(sx, sy), s.second + 1));
						visited[sx][sy] = true;
					}
				}
				if (ch) break;
			}
			if (ch) break;
		}
		if (ch) continue;
		cout << "IMPOSSIBLE\n";
	}
}

문제 : https://www.acmicpc.net/problem/2075

[알고리즘풀이]

메모리 제한이 10MB로 N * N 개의 수를 전부 저장한다음 Sorting하고 N번 째 큰 수를 출력한다면 '메모리 초과'를 받게 된다.

N * N 개의 수 중에서 N번 째로 큰 수를 출력하는 문제를 바꿔생각하면 들어온 입력 중 크기가 큰 순서대로 N개의 수만 기억하고 있으면 답을 출력할 수 있다.

즉, N개의 수를 N번 입력받으면서 지금까지 입력된 수 중에서 큰 순서대로 N개만 저장하는 알고리즘을 구현해야한다.

1차원 배열을 선언해서 문제를 해결할 수도 있지만, 자료구조 우선순위큐(Priority_Queue)를 이용하면 간단하게 알고리즘을 구현할 수 있다.

[예시]

-Input

5

12 7 9 15 5

13 8 11 19 6

21 10 26 31 16

48 14 28 35 25

52 20 32 41 49

-Priority_Queue

-Output

35

[소스코드]

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int x,n;
	priority_queue<int, vector<int>, greater<int>> pq;
	cin >> n;
	for(int j = 0; j < n; j++){
		cin >> x;
		pq.push(x);
	}
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> x;
			if (x > pq.top()) {
				pq.pop();
				pq.push(x);
			}
		}
	}
	cout << pq.top();
}

문제 : https://www.acmicpc.net/problem/2023

[알고리즘풀이]

처음에는 에라토스테네스 체로 모든 소수를 구해놓고,

모든 N자리 숫자에 k에 대해 k를 뒤에서부터 자릿수를 날려가며 소수인지 아닌지 판별해서 출력했습니다.

하지만, 이 문제는 메모리 제한이 4MB로 극악의 메모리 제한을 가지고 있어, 메모리 제한 문제에 걸렸습니다.

문제에서 원하는 소수는 맨 뒤부터 자릿수를 날렸을 때, 모두 소수여야 되므로

맨 앞 자릿수가 2,3,5,7이어야 되고 나머지 자리도 1,3,5,7,9 중에 하나여야만 가능합니다.

이 특징을 이용하면 메모리 제한을 해결할 수 있습니다. 

백트레킹을 활용해서 모든 경우에 대해서 구했고, 중간에 소수가 아니면 백트레킹을 컷팅했습니다.

#include<iostream>
#include<vector>

using namespace std;

int n;
int p[4] = { 2,3,5,7 };
int o[5] = { 1,3,5,7,9 };

void bt(int s, int k) {
	if (k == n) {
		cout << s << '\n';
		return;
	}
	for (int i = 0; i < 5; i++) {
		bool check = false;
		s *= 10;
		s += o[i];
		for (int j = 2; j * j <= s; j++)
			if (s % j == 0){ // 소수가 아니라면 컷팅
				check = true; break;
			}
		if(!check)
			bt(s, k + 1);
		s -= o[i];
		s /= 10;
	}
	return;
}

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

	cin >> n;
	for (int i = 0; i < 4; i++) {
		bt(p[i], 1);
	}
	
	return 0;
}

문제 : https://www.acmicpc.net/problem/6679

[알고리즘풀이]

1000 ~ 9999까지 10, 12, 16진수로 표현하면서 자릿수를 다 더해주고 같다면 출력, 아니라면 출력 X

#include<iostream>

using namespace std;

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

	int a, b, c, j ;
	for (int i = 1000; i <= 9999; i++) {		
		a = 0, b = 0, c = 0;
		j = i;
		while (j != 0) {
			a += j % 10;
			j /= 10;
		}
		j = i;
		while (j != 0) {
			b += j % 12;
			j /= 12;
		}
		j = i;
		while (j != 0) {
			c += j % 16;
			j /= 16;
		}
		if (a == b && b == c)
			cout << i << '\n';
	}
	return 0;
}