boj, 백준) 9205. 맥주 마시면서 걸어가기 ( C / C++)

1. 문제 링크

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

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

2. 문제 개요

집에서 락 페스티벌로 가려고 한다. 맥주를 마시면서 걸어간다. 맥주 한 박스에는 맥주 20개가 들어있다. 목이 마르면 안 되기 때문에 50m에 한 병씩 마시려고 한다. 페스티벌에 도착할 수 있는지 구하는 프로그램을 만들자.

 

3. 문제 힌트

   50m고 20캔있으니 1000m 이내에 있다면 간선으로 연결해주자.

그리고 주어진 맵에서 집 - 락페스티벌까지의 경로가 있다면 갈 수 있는 것이다.

 

4. 문제 풀이

(3) 번에 작성한 내용대로 구현하기만 하면 되는 간단한 문제다.

간선을 연결하고 시작점을 집으로 두고 BFS를 사용했다.

최종적으로 락 페스티벌에 방문한 적이 있다면 happy를 출력하고 그렇지 않다면 sad를 출력한다.

 

5. 코드

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

struct COORD {
	int y, x;
	int vertex;
};

int main(void)
{
	int t;
	scanf("%d", &t);
	
	while (t--)
	{
		int dist[102][102] = { 0 };
		COORD c[102];
		bool visited[102] = { false, };
		//0->집  n+1 -> 페스티벌

		int n;
		scanf("%d", &n);
		for (int i = 0; i <= n + 1; i++) {
			scanf("%d %d", &c[i].x, &c[i].y);
			c[i].vertex = i;
		}
		

		for (int i = 0; i <= n + 1; i++)
		{
			for (int j = i; j <= n + 1; j++)
			{
				if (i == j)
					dist[i][j] = 0;
				else
				{
					int val;
					val = abs(c[i].x - c[j].x) + abs(c[i].y - c[j].y);
					if (val > 1000)
						dist[i][j] = dist[j][i] = 0;
					else
						dist[i][j] = dist[j][i] = 1;
				}
			}
		}
		//맵 완성
		queue<COORD> q;

		q.push(c[0]);
		visited[0] = true;

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

			for (int i = 0; i <= n + 1; i++)
			{
				if (dist[cur.vertex][i] == 1 && visited[i] == false)
				{
					visited[i] = true;
					q.push(c[i]);
				}
			}
		}

		if (visited[n + 1])
			printf("happy\n");
		else
			printf("sad\n");

	}
	return 0;
}

 

지적, 댓글 언제나 환영입니다~