백준 9205 - 맥주 마시면서 걸어가기(C++)

문제 링크입니다 https://www.acmicpc.net/problem/9205

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

문제 조건

출력 예시

BFS를 이용해 갈 수 있는 편의점에 들리면서, 도착점에 갈 수 있는지를 확인하는 문제였습니다.

편의점에 들릴 때마다 맥주의 갯수를 20개로 계속 바꾸어줘야 했습니다.

 

문제 접근 방법

1. 출발점, 도착점, 편의점의 위치를 pair로 받는다.

2. 위치 + 맥주의 갯수를 담을 수 있는 구조체를 선언한 뒤, 큐로 만들어준다.

3. 출발점에서 N개의 편의점 중, 갈 수 있는 곳을 찾은뒤, 해당 위치로 이동한다.

4. 현재 위치에서 도착점을 갈 수 있는지를 계속 확인해준다.

5. 1~4번을 Test_case만큼 반복한다. 

 

문제 접근 방법(2번 + 3번 + 4번)

bool bfs() {
	queue<qu> q;
	q.push({ start.first, start.second, 20 });
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int remain = q.front().remain;
		q.pop();
		if (abs(x - finish.first) + abs(y - finish.second) <= remain * 50) {
			return true;
		}
		for (int i = 1; i <= N; i++) {
			if (check[i] == 0) {
				int dis = abs(x - store[i].first) + abs(y - store[i].second);
				if (dis <= remain * 50) {
					check[i] = 1;
					q.push({ store[i].first,store[i].second,20 });
				}
			}
		}
	}
	return false;
}

출발점의 위치와 맥주 20개를 queue에 넣어준 뒤, N개의 편의점 중에서 갈 수 있는 곳을 찾아줍니다.

abs(x-y)를 하면 x-y의 값이 절대값으로 나옵니다. 이를 이용해서 위치를 구했습니다. 

queue에 넣어진 좌표와 맥주의 갯수를 이용해 도착점에 도착할 수 있는지를 계속 확인해줍니다.

탐색 도중 도착점에 도착했다면 return true를 했으며, 탐색을 마쳤는데도 도착하지 못했을 경우 return false를 해줬습니다.

 

자세한 것은 코드를 참고해세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

int test_case, N;
pair<int, int> start, finish, store[101];
int check[101];
typedef struct qu {
	int x;
	int y;
	int remain;
}qu;

bool bfs() {
	queue<qu> q;
	q.push({ start.first, start.second, 20 });
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int remain = q.front().remain;
		q.pop();
		if (abs(x - finish.first) + abs(y - finish.second) <= remain * 50) {
			return true;
		}
		for (int i = 1; i <= N; i++) {
			if (check[i] == 0) {
				int dis = abs(x - store[i].first) + abs(y - store[i].second);
				if (dis <= remain * 50) {
					check[i] = 1;
					q.push({ store[i].first,store[i].second,20 });
				}
			}
		}
	}
	return false;
}

void solve() {
	bool ans = bfs();
	if (ans) cout << "happy" << "\n";
	else cout << "sad" << "\n";
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for (int k = 0; k < test_case; k++) {
		cin >> N;
		cin >> start.first >> start.second;
		for (int i = 1; i <= N; i++) {
			cin >> store[i].first >> store[i].second;
		}
		cin >> finish.first >> finish.second;
		solve();
		memset(check, 0, sizeof(check));
	}
	return 0;
}

 

질문 및 조언 댓글 남겨주세요!