PS

[C++] 9205: 맥주 마시면서 걸어가기

왕방토 2022. 6. 29. 20:05
728x90

실버 Ⅰ

 

bfs로 푼 코드

#include <iostream>
#include <queue>
#include <vector>
#define ABS(x) ((x<0)?(-x):(x))
using namespace std;

struct P {
	int x, y;
};

int N;

P house;
P fest;
vector<P> cu;//0 안씀
bool visit_cu[101];// 0 안씀
bool is_happy = false;

void bfs() {
	queue<P> q;
	q.push(house);

	while (!q.empty()) {
		P cur = q.front();
		q.pop();

		int cur_to_fest = ABS((cur.x - fest.x)) + ABS((cur.y - fest.y));
		if (cur_to_fest <= 1000) {
			is_happy = true;
			return;
		}

		for (int next_idx = 1; next_idx <= N; next_idx++) {
			if (visit_cu[next_idx]) continue;
			P next = cu[next_idx];

			int cur_to_next = ABS((cur.x - next.x)) + ABS((cur.y - next.y));
			if (cur_to_next <= 1000) {
				visit_cu[next_idx] = true;
				q.push(cu[next_idx]);
			}
		}
	}
}

void init_ds() {
	cu.clear();
	cu.push_back({0, 0});//안씀
	is_happy = false;
	for (int i = 0; i <= N; i++)
		visit_cu[i] = false;
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		init_ds();
		scanf("%d", &N);

		scanf("%d%d", &house.x, &house.y);
		int a, b;
		for (int i = 1; i <= N; i++) {
			scanf("%d%d", &a, &b);
			cu.push_back({ a, b });
		}
		scanf("%d%d", &fest.x, &fest.y);

		bfs();

		if (is_happy) printf("happy\n");
		else printf("sad\n");
	}
}

 

 

dfs로 푼 코드

#include <iostream>
#include <queue>
#include <vector>
#define ABS(x) ((x<0)?(-x):(x))
using namespace std;

struct P {
	int x, y;
};

int N;

P house;
P fest;
vector<P> cu;//0 안씀
bool visit_cu[101];// 0 안씀
bool is_happy = false;

void dfs(bool is_house, int cu_idx) {
	P here;
	if (is_house) here = house;
	else here = cu[cu_idx];

	int here_to_fest = ABS((here.x - fest.x)) + ABS((here.y - fest.y));
	if (here_to_fest <= 1000) {
		is_happy = true;
		return;
	}

	for (int next_idx = 1; next_idx <= N; next_idx++) {
		if (visit_cu[next_idx]) continue;
		P next = cu[next_idx];
		int here_to_next = ABS((here.x - next.x)) + ABS((here.y - next.y));
		if (here_to_next <= 1000) {
			visit_cu[next_idx] = true;
			dfs(false, next_idx);
		}
	}
}

void init_ds() {
	cu.clear();
	cu.push_back({0, 0});//안씀
	is_happy = false;
	for (int i = 0; i <= N; i++)
		visit_cu[i] = false;
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		init_ds();
		scanf("%d", &N);

		scanf("%d%d", &house.x, &house.y);
		int a, b;
		for (int i = 1; i <= N; i++) {
			scanf("%d%d", &a, &b);
			cu.push_back({ a, b });
		}
		scanf("%d%d", &fest.x, &fest.y);

		dfs(true, 0);

		if (is_happy) printf("happy\n");
		else printf("sad\n");
	}
}

 

처음에 보니까 거리라서 으아악 했는데 택시거리라서 휴~ 했다

문제 요약하면 아래와 같다!

9205 요약

dfs 코드는... 근데 이 문제는 dfs로 풀면 좀 직관적인 이해가 어렵다

visit을 체크해주는 이유는..

만약 cu[3]을 갔다고 하면

cu[3]에서 dfs로의 루트를 다 찾았을 테니

또 cu[3]에서 탐색을 시작해주지 말라고 하는 그냥 dfs 기본 의미인 visit 이다

 

근데 이게 그냥 일반 dfs 그래프처럼

고정된 그래프 형태가 아니니까...

연결 형태(간선)이 바뀌지 않는 일반적인 dfs 그래프

현재 노드가 무엇이냐(cu[x])에 따라서 갈 수 있는 노드들이 유동적으로 바뀌어서

암튼 그런거 생각하면 dfs는 좀 직관적으로 이해가 안됨

 

근데 사실

https://www.acmicpc.net/board/view/53009

 

글 읽기 - 맞았는데 이문제가 BFS로 풀어야하는 이유가 궁금합니다.

댓글을 작성하려면 로그인해야 합니다.

www.acmicpc.net

이거 보면 이런 류의 문제는 dfs로 풀면 시간초과가 날 수도 있는 문제라

이 문제에서는 그냥 테케가 dfs 시간초과가 안나는 테케들만 있어서 통과한 것 같기도 하다

댓글수0