굳건하게

안녕하세요, 여행벌입니다.

C언어로 쉽게 풀어 쓴 자료구조 1장 - 자료구조와 알고리즘 연습문제 풀이입니다.

틀린 부분은 같이 댓글로 얘기해보면 좋을 것 같습니다!

안녕하세요, 여행벌입니다.

이산수학 Express(2011) 2장 - 논리와 명제 연습문제 풀이입니다.

틀린 부분은 같이 댓글로 얘기해보면 좋을 것 같습니다!

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

BOJ 5427번 문제와 매우 유사하다.

BFS 탐색을 불을 먼저 다 이동하고, 사람을 이동하면서 진행하면 된다.

#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  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 >> r >> c;
	for (int i = 0; i < r; i++)
		cin >> map[i];

	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] == 'F')
				fire.push(make_pair(i, j));
			if (map[i][j] == 'J') {
				q.push(make_pair(make_pair(i, j), 0));
				visited[i][j] = true;
				map[i][j] = '.';
			}
		}

	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] = 'F';
					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';
					return 0;
				}
				if (map[sx][sy] == '.' && visited[sx][sy] == false) {
					q.push(make_pair(make_pair(sx, sy), s.second + 1));
					visited[sx][sy] = true;
				}
			}
		}

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

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

[알고리즘풀이]

모든 1 ~ N 개의 컴퓨터에 대해서 BFS 탐색을 다 진행해 최대 탐색 가능한 컴퓨터 수를 저장한다.

그 후, 가장 큰 값을 가지고 있는 컴퓨터들만 출력하면 된다.

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

using namespace std;

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

	int n, m, x, y;
	vector<int> P[10001];
	int answer[10001] = {};
	
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		P[y].push_back(x);
	}

	int total_max = -1;
	// 1 ~ n 번까지 다 시작해보자.
	for (int i = 1; i <= n; i++) {
		// i 번에서 시작해서 BFS 탐색으로 최대 탐색 가능한 컴퓨터 수를 저장.
		int c = 1; 
		bool visited[10001] = {};
		queue<int> q;
		q.push(i);
		visited[i] = true;
		while (!q.empty()) {
			int s = q.front();
			q.pop();
			for (int j = 0; j < P[s].size(); j++) {
				if (visited[P[s][j]] == false) {
					visited[P[s][j]] = true;
					q.push(P[s][j]);
					c++;
				}
			}
		}
		answer[i] = c;
		total_max = max(total_max, c);
	}
	for (int i = 1; i <= n; i++)
		if (total_max == answer[i])
			cout << i << ' ';
}