백준 9205. 맥주 마시면서 걸어가기

게시 2025/09/15

By Dukgukim

7 분읽는 시간

경로 탐색 문제

문제 분석

집에서 출발하여 목적지에 도달해아한다
맥주 한박스에는 20개가 들어있다.
- 50미터에 한 병씩 마신다. 50미터를 가려면, 그 직전에 한 병을 마셔야한다
맥주를 더 구매해야 할 수도 있다. 추가 맥주는 편의점에서 맥주 구매 가능
- 빈 병은 버리고, 새 맥주병을 살 수 있다.
- 박스에 들어있는 맥주는 20병을 넘을 수 없다
- 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한병을 마셔야한다
편의점, 집, 목적지의 좌표가 주어졌을때, 도착할 수 있는지 여부를 구하는 문제

입력

테스트 케이스의 개수 T가 주어짐 (T<=50)
각 테스트케이스의 첫째줄에는 맥주를 파는 편의점의 개수 N이 주어짐 (0<=N<=100)
N+2개 줄에는 상근이의 집, 편의점, 펜타포트 락 페스티벌의 좌표가 주어짐 (-32768 <= X, Y <= 32767)
송도는 직사각형으로 생긴 도시, 두 좌표 사이의 거리는 맨해튼 거리를 따른다

출력

각 테스트케이스에 대해 목적지에 도달할 수 있으면 “happy”, 맥주가 모자르면 “sad”를 출력

예시 분석

1) tc1

상근이의 집 : (0,0), 편의점은 2개 : (1000,0), (1000,1000) 목적지 : (2000, 1000)

(0,0)에서 첫번째 편의점으로 이동하는데 맥주 20개 써서 (1000,0)에 도달 가능 맥주 리필하고 두번째 편의점 (1000,1000) 도착 두번째 편의점에서 또 리필하고 목적지(2000,1000)에 도달 가능하므로 “happy” 출력

2) tc2

첫번째 편의점에서 두번쨰 편의점으로 도달이 불가능하므로 “sad” 출력

알고리즘

중간 정거장이 있는 경로 탐색 문제

한번에 이동할 수 있는 거리가 맥주20개 만큼이므로, 이 거리 내에 정거장이 없으면 도달 불가능함

1. Blood-Fill을 이용한다면?

blood-fill 이용해서 거리 내에 목적지가 있으면 탐색 종료, 편의점이 있다면 충전하는 식으로 접근

그렇다면, 중복 탐색 방지를 위해 방문처리용 변수가 필요한데

가능한 좌표는 (-32768 ≤ x, y ≤ 32767)이므로, bool visited[65535][65535]가 된다

1byte * 2^16 * 2^16 = 2^32 byte = 약 4GB이므로, 방문처리하면 메모리 초과가 발생하므로 다른 방법 필요

2. 그래프 탐색 이용

4방향으로 이동하는게 아니라, 의미있는 지점들만을 그래프의 노드라고 생각하고 이동

두 노드 사이의 거리가 1000m이하면(맥주 20병) 간선이 연결되어있다고 봄

각 노드의 좌표 기록을 Node로 받고, 연결 간선만 따로 Edge 벡터에 저장
아니면 해당 노드로 이동했을때, 실시간으로 거리를 계산하고 접근

1. TC 입력 받기
2. TC 수행
	2-1. 초기 좌표들을 하나의 벡터에저장 
		- 연결 간선 정보들을 <Edge>노드에 저장
		- 간선 연결 구축하기
	2-2. BFS에 시작위치(집)을 넣고 BFS 시작
	- 큐에서 맨 앞 노드 꺼내기
		- 목적지라면 "happy"
	- 이 노드와 연결된 노드 검색
		- 거리가 1000m 이내인 노드가 있는지 체크
		- 그 노드가 방문한적 있는지 체크
		- 방문한적 없다면 방문처리 후, 큐에 넣기

소스코드

  
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N;
vector< pair<int, int> > v;

void Input() {
	
	// init
	v.clear();

	// input
	cin >> N;
	// 집, 편의점, 락페 좌표
	for (int i = 0; i < N + 2; i++) {
		int yy, xx;
		cin >> yy >> xx;
		v.push_back({ yy,xx });
	}
}

void BFS() {
	bool visited[105] = { 0 };
	queue<int> qu;
	qu.push(0);
	visited[0] = true;

	while (!qu.empty()) {
		int now_y = v[qu.front()].first;
		int now_x = v[qu.front()].second;
		qu.pop();

		// 목적지. 벡터 맨 마지막 원소에 저장되어있음
		if (now_y == v.back().first && now_x == v.back().second) {
			cout << "happy\n";
			return;
		}

		// 다음노드 검색
		for (int i = 1; i < v.size(); i++) {
			if (visited[i] == true) continue; // 이미 방문했음

			int dy = v[i].first, dx = v[i].second;
			int dist = abs(now_y - dy) + abs(now_x - dx);
			if (dist > 1000) continue; // 거리가 1000m 초과

			visited[i] = true;
			qu.push(i); 
		}
	}
	cout << "sad\n";
	return;
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	int TC; cin >> TC;
	while (TC--) {
		Input();

		BFS();
	}
	
	return 0;
}

현재 문제에서는 노드가 100개 미만이라 실시간으로 거리를 계산해도 상관없지만,

노드가 수천~수만개에 이른다면 이 경로를 매 탐색마다 계산하는게 오버헤드가 발생할 수 있을 것 같다.

이때는 사전에 입력을 받으면서 인접리스트나 배열로 간선을 정리하는게 더 나을것 같다

Algorithm, Problem Solving