[백준] 9205번 - 맥주 마시면서 걸어가기 (카스텐라우프)

 

https://www.acmicpc.net/problem/9205

9205번: 맥주 마시면서 걸어가기

✏️원리 

Kastenlauf 

카스텐라우프는 독일에서 주로 하는 술게임이라고 한다.

 

이 문제는 위 게임과 룰이 같으며,

맥주 20병을 담을 수 있는 박스를 들고 페스티벌까지 50m씩 맥주를 마시면서 맥주가 동이 안 날 때까지 마시면서 갈 수 있는지 없는지를 해결해야 하는 문제이다.

 

이 문제를 보고 나서 처음에 DFS로 풀어야지하며, DFS로 풀어보았다.

하지만 계속 시간초과가 나와, 계속 시간을 단축해가면서 해결하려 했지만, 해결이 안 됐었다.

(누가 DFS로 시간 초과 안 나도록 해결할 수 있는 방법을 알고 있으시면 댓글 남겨주세요 ㅠ)

 

📃 DFS로 풀어본 소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;


int N;

int startx, starty;
int endx, endy;
vector<pair<int, int>> cs;
bool ok;

void dfs(int x, int y, vector<bool> visited) {
	
	if (!ok) {
		if (abs(endx - x) + abs(endy - y) <= 1000) {
			ok = true;
			return;
		}



		for (int i = 0; i < N; ++i) {
			if (visited[i] == false && abs(cs[i].first - x) + abs(cs[i].second - y) <= 1000) {
				visited[i] = true;
				dfs(cs[i].first, cs[i].second, visited);
			}
		}
	}
	

	return;
	
}


int main() {


	
	int tc;
	scanf("%d", &tc);
	while (tc--) {
		scanf("%d", &N);
		scanf("%d %d", &startx, &starty);
		cs.clear();
		for (int i = 0; i < N; ++i) {
			int x, y;
			scanf("%d %d", &x, &y);
			cs.push_back(make_pair(x, y));
		}
		scanf("%d %d", &endx, &endy);
		vector<bool> visited;

		visited = vector<bool>(N, false);
		ok = false;
		dfs(startx, starty, visited);

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


}

 

그래서 다른 방법을 고민을 하다가, 표를 보고 BFS로도 풀린다는 것을 다행이도 알아차렸었다.

 

BFS를 이용해서 마지막 도착지에 도착을 했냐 안했냐를 반환해준 불린으로 happy, sad를 출력해주면 간단한 문제였다.

DFS로 헛수고했었지만, BFS로 풀어보니 정말 간단한 문제였고 손쉽게 코드를 쓸 수 있었다.

 

 

 

📃 구현 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
using namespace std;


int N;

int startx, starty;
int endx, endy;
vector<pair<int, int>> cs;

bool bfs(int x, int y) {
	
	vector<bool> visited;
	visited = vector<bool>(N+2, false);
	
	visited[0] = true;

	queue<pair<int, int>> q;
	q.push(make_pair(x, y));

	while (!q.empty()) {
		int here_x = q.front().first;
		int here_y = q.front().second;
		q.pop();

		for (int i = 1; i < N + 2; ++i) {
			int there_x = cs[i].first;
			int there_y = cs[i].second;

			if (visited[i] == false && (abs(there_x - here_x) + abs(there_y - here_y) <= 1000)) {
				q.push(make_pair(there_x, there_y));
				visited[i] = true;
			}
		}

	
	}


	return visited[N+1];
	
}


int main() {


	
	int tc;
	scanf("%d", &tc);
	while (tc--) {
		scanf("%d", &N);
		scanf("%d %d", &startx, &starty);

		cs.clear();
		cs.push_back(make_pair(startx, starty));
		for (int i = 0; i < N; ++i) {
			int x, y;
			scanf("%d %d", &x, &y);
			cs.push_back(make_pair(x, y));
		}
		scanf("%d %d", &endx, &endy);
		cs.push_back(make_pair(endx, endy));
		
		
		bool res = bfs(startx, starty);
		
		if (res) {
			printf("happy\n");
		}
		else {
			printf("sad\n");
		}
	}


}

 

궁금하신 것이 있으시면 언제든지 댓글 달아주세요!