[BAEKJOON] 17266, 18352

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

 

[sliver4, 17266 어두운 굴다리] - 이분탐색

문제에서 요구하는 결과 값은 "가로등의 높이"이다.
이를 pivot으로 두고 이분탐색을 진행하며, 
가로등이 굴다리 전체를 비추고있는지 그렇지 않은지를 판단하여 mid값을 조정한다.

굴다리 전체가 비춰지고 있다면, 현재 mid값은 최적이거나 너무 높은것이므로 right를 줄이고
굴다리 전체가 비춰지지 않고 있다면, 현재 mid값은 너무 낮은것이므로 left를 높인다.
최적의 해를 찾아야하므로 left와 right가 동등할 때 까지 판단하는 것이 좋다.

굴다리가 비춰지는지 판단하기 위한 핵심은 가로등을 기준으로
이전의 가로등(prev)가 비추는 오른쪽 끝값과, 이후의 가로등(next)가 비추는 왼쪽 끝값을 비교하여
겹쳐지지 않는 구간이 존재한다면 굴다리가 안비춰지고 있는 것이다.
또한, 시작 및 끝 구간에 대해 0과 N을 기준으로 
가로등 높이에 따른 예외처리를 먼저 진행해 준다면 더 쉽게 구현할 수 있을 것이다.

#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;

int N, M, lamp[100001];

bool checkLamp(int h) {
	if (0 < lamp[0] - h) return false;
	if (lamp[M - 1] + h < N) return false;
	int prev = lamp[0] + h;
	for (int m = 1; m < M; m++) {
		int next = lamp[m] - h;
		if (prev < next) return false;
		prev = lamp[m] + h;
	}
	return true;
}

int main() {
	scanf("%d", &N);
	scanf("%d", &M);
	for (int m = 0; m < M; m++)
		scanf("%d", &lamp[m]);

	int left = 1;
	int right = 100000;
	int res = 100000;
	while (left <= right) {
		int mid = (left + right) / 2;
		printf("%d, %d -> %d\n", left, right, mid);
		if (checkLamp(mid)) {
			res = min(res, mid);
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	printf("%d", res);
}

 

[sliver2, 18352 특정 거리의 도시 찾기] - BFS(너비 우선 탐색)

간단하게 구현할 수 있으나, X에서 X로가는 최단거리는 항상 0임에 유의하라.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;

int N, M, K, X;
int st, ed;
bool visit[1000001];

typedef struct data {
	int city, cnt;
}Data;

vector<int> answer;
int main() {
	scanf("%d %d %d %d", &N, &M, &K, &X);
	
	vector<vector<int>> load(N + 1);
	for (int m = 0; m < M; m++) {
		scanf("%d %d", &st, &ed);
		load[st].push_back(ed);
	}

	queue<Data>q;
	q.push({ X, 0 });
	visit[X] = true;
	while (!q.empty()) {
		Data out = q.front(); q.pop();
		if (out.cnt == K) {
			answer.push_back(out.city);
			continue;
		}
		for (int i = 0; i < load[out.city].size(); i++) {
			int next_city = load[out.city][i];
			int next_cnt = out.cnt + 1;
			if (!visit[next_city]) {
				visit[next_city] = true;
				q.push({ next_city, next_cnt });
			}
		}
	}
	if (answer.empty()) {
		printf("-1");
		return 0;
	}
	sort(answer.begin(), answer.end());
	for (int i = 0; i < answer.size(); i++) {
		printf("%d\n", answer[i]);
	}
}