굳건하게

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

플로이드와샬 경로탐색

 키 순서를 입력으로 받아 그래프를 그린다고 생각하자. 그러면 i번 사람에서 j번 사람으로 경로가 있다면, j번 사람이 i번 사람보다 확실히! 키가 크다는 걸 의미한다. 따라서, 우리는 K번 사람이 다른 모든 사람들과 경로가 존재한다면 키 순서를 확실히 알 수 있다. 따라서, 플로이드와샬 알고리즘으로 모든 사람에 대해서 경로를 구하고, K번 사람이 다른 모든 사람들에게 갈 수 있거나, 혹은 다른 사람들이 K번 사람으로 올 수 있는 경로가 있다면 키 순서를 확실히 알 수 있는 사람으로 간주하면 된다.

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

const int INF = 99999999;
int map[501][501];

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

	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			map[i][j] = INF;
	for (int i = 1; i <= N; i++)
		map[i][i] = 0;

	for (int i = 0, x, y; i < M; i++) {
		cin >> x >> y;
		map[x][y] = 1; // x -> y
	}

	// 플로이드와샬
	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		bool check = true;
		for (int j = 1; j <= N; j++)
			if (map[i][j] == INF && map[j][i] == INF) {
				check = false;
				break;
			}
		if (check)
			ans++;
	}
	cout << ans;
	return 0;
}

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

BFS

● BFS 탐색을 진행하는데 벽을 몇 번 부수고 현재 지점에 도달했는지 체크하기위해 3차원 visited 배열을 사용하면 된다.

● visited[x][y][w] := (x, y) 지점에 w만큼의 벽을 부수고 도달

● 현재 지점에서 이동할 다음 칸이 벽이 아니고 방문하지 않았다면 큐에 push.

    현재 지점에서 이동할 다음 칸이 벽이라면

    - 낮인 경우, 이동할 칸에 현재 벽 부순 횟수 + 1 상태로 방문한 적이 없다면 큐에 push

    - 밤인 경우, 이동할 칸에 현재 벽 부순 횟수 + 1 상태로 방문한 적이 없다면 큐에 현재 위치를 push

#include<iostream>
#include<queue>

using namespace std;

struct node {
	int x, y, t, w; // x좌표 y좌표 벽부순횟수 시간
};

int N, M, K, dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
char map[1000][1001];
bool visited[1000][1000][11] = {};

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

	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
		cin >> map[i];

	queue<node> q;
	q.push({ 0, 0, 0, 0});
	visited[0][0][0] = 1;

	int ans = -1;
	while (!q.empty()) {
		int curX = q.front().x, curY = q.front().y;
		int curTime = q.front().t, curW = q.front().w;
		q.pop();
		if (curX == N - 1 && curY == M - 1) {
			ans = curTime + 1;
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i], nextY = curY + dy[i];
			if (!(0 <= nextX && nextX < N && 0 <= nextY && nextY < M))
				continue;
			if (map[nextX][nextY] == '0' && !visited[nextX][nextY][curW]) {
				visited[nextX][nextY][curW] = 1;
				q.push({ nextX, nextY, curTime + 1, curW });
			}
			if (map[nextX][nextY] == '1' && curTime % 2 == 0 && curW + 1 <= K && !visited[nextX][nextY][curW + 1]) {
				visited[nextX][nextY][curW + 1] = 1;
				q.push({ nextX, nextY, curTime + 1, curW + 1});
			}
			if (map[nextX][nextY] == '1' && curTime % 2 == 1 && curW + 1 <= K && !visited[nextX][nextY][curW + 1]) {
				q.push({ curX, curY , curTime + 1, curW });
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

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

DP BFS

BFS 탐색에 DP를 적용해서 문제를 해결했습니다.

● DP[X] := start에서 시작해 X 지점에 오는데 필요한 최소 이동 횟수.

● 내가 현재 지점(x) 에서 점프 횟수가 y일 때, 다음에 이동할 지점의 DP 값이 y + 1 보다 작으면 최소 이동 횟수가 아니므로 점프를 하지 않고, 또 y + 1이 현재 정답(end에 오는데 필요한 최소 점프 횟수) 보다 크면 최소 이동 횟수가 아니므로 점프를 하지 않아도 됩니다.

#include<iostream>
#include<queue>
#define INF 99999999
using namespace std;

int dp[200001] = {};

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

	int N, K, ans = INF, cnt = 0;
	cin >> N >> K;

	queue<pair<int, int>> q;
	q.push({ N, 0 });
	for (int i = 0; i < 200001; i++)
		dp[i] = INF;

	while (!q.empty()) {
		pair<int, int> cur = q.front(); 
		q.pop();
		if (cur.first == K) {
			ans = min(ans, cur.second);
			if (ans == cur.second)
				cnt++;
		}
		if (0 <= cur.first - 1 && cur.second + 1 <= dp[cur.first - 1] && cur.second + 1 <= ans){
			dp[cur.first - 1] = cur.second + 1;
			q.push({ cur.first - 1, cur.second + 1 });
		}
		if (cur.first + 1 <= K && cur.second + 1 <= dp[cur.first + 1] && cur.second + 1 <= ans){
			dp[cur.first + 1] = cur.second + 1;
			q.push({ cur.first + 1, cur.second + 1 });
		}
		if (cur.first * 2 <= 200000 && cur.second + 1 <= dp[cur.first * 2] && cur.second + 1 <= ans){
			dp[cur.first * 2] = cur.second + 1;
			q.push({ cur.first * 2, cur.second + 1 });
		}
	}
	cout << ans << '\n' << cnt;
	return 0;
}

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

이분탐색

 N x N 행렬의 i 번 째 행을 보면 i번 째 구구단인 것을 알 수 있습니다. 따라서, i번 째 행에서 어떤 값 x 보다 작거나 같은 수는 x / i 를 통해 구할 수 있습니다. 주의할 점은 예를 들어 N이 5이면 3번 째 행은 3 6 9 12 15 가 된다. 이때 18보다 작거나 같은 수를 18 / 3 으로 구해버리면 하나가 더 카운트 된다. 즉 i번 째 행에서 얻을 수 있는 갯수는 최대 N개 이므로 i번 째 행에서 x 보다 작거나 같은 수는 min( x / i , N ) 으로 구할 수 있다.

따라서, 다음과 같은 식을 만들 수 있다.

F(x) := N x N 행렬에서 x 보다 작거나 같은 숫자의 갯수

       := 1 ~ N 까지의 수로 x 를 나눈 값과 N 중 더 작은 값을 다 더한다.

이때, 정의상 F(x) 는 단조증가함수가 되므로 이분탐색을 이용할 수 있다.

#include<iostream>
#include<algorithm>

using namespace std; 

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

	int result = 0;
	int left = 1, right = K;
	while (left <= right) {
		int mid = (left + right) / 2;
		int cnt = 0;
		for (int i = 1; i <= N; i++) { // cnt에는 mid보다 작거나 같은 애들 담김.
			cnt += min(mid / i, N);
		}
		 if (cnt < K) // mid로는 아직 부족함.
			left = mid + 1;
		else{ // mid로 충분할 수도 있고, 더 작아질 수도 있으므로 일단 저장.
			result = mid;
			right = mid - 1;
		 }
	}
	cout << result << '\n';
	return 0;
}