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

문제는 링크로 대체합니다.

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

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

문제를 간략히하면 출발점에서 도착점으로 도달할 수 있느냐를 결정하는 것입니다. 맥주를 50m마다 마시고 20병의 제한이 있다는둥 뭔가 있어보일듯하게 문제를 설명하였지만 핵심만을 파악하여야 합니다. 이동간에 맥주를 얼만큼 마시든 편의점을 들릴수만 있다면 다시 20병으로 가득 채울 수 있기 때문에 입력을 노드 그래프로 표현해보면 각 편의점이 하나의 노드가 되고 서로 다른 편의점 간의 거리가 1000이하인 곳은 양방향의 길이 있다고 생각하면 됩니다. 그래서 입력을 통해 간선정보를 저장한뒤에 bfs혹은 dfs로 경로탐색을 통해 도착노드에 도달할 수 있다면 happy를 없다면 sad를 출력하면 됩니다.

 

그래서 각 편의점당 이동이 가능한 편의점들을 저장하기 위해 vector<편의점번호> map[MAX_N] 을 사용하였고 간선들을 저장한 후에는 bfs를 수행하였습니다.

 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <queue>

using namespace std;
#define MAX_T 50
#define MAX_N 102

int T, N;

pair<int, int> conv[MAX_N];//각 위치의 좌표를 저장.
vector<int> map[MAX_N];//이동이 가능한 지점의 인덱스를 저장.
int visit[MAX_N];
int result[MAX_T];

bool happy_sad() {
	int now_node;
	queue<int> q;
	q.push(0);
	while (q.empty() == false) {
		now_node = q.front();
		//printf("node %d\n", now_node);
		if (now_node == N + 1) {
			return true;
		}
		q.pop();
		visit[now_node] = 1;
		for (int i = 0; i < map[now_node].size(); i++) {
			if (visit[map[now_node][i]] == 0) {
				q.push(map[now_node][i]);
			}
		}
	}
	return false;
}

void clear() {
	for (int i = 0; i < N + 2; i++) {
		visit[i] = 0;
		map[i].clear();
	}
}

int main()
{
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		scanf("%d", &N);
		for (int j = 0; j < N + 2; j++) {
			scanf("%d %d", &conv[j].first, &conv[j].second);
			for (int k = 0; k < j; k++) {
				int man_dis = abs(conv[k].first - conv[j].first) + abs(conv[k].second - conv[j].second);
				if (man_dis <= 1000) {
					map[j].push_back(k);
					map[k].push_back(j);
				}
			}
		}


		//for (int i = 0; i < N + 2; i++) {
		//	for (int j = 0; j < map[i].size(); j++) {
		//		printf("%d ", map[i][j]);
		//	}
		//	printf("\n");
		//}

		result[i] = happy_sad() ? 1 : 0;
		clear();
	}

	for (int i = 0; i < T; i++) {
		result[i] ? printf("happy\n") : printf("sad\n");
	}
}