[백준/C언어]9205번 맥주 마시면서 걸어가기

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

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

 

• 접근 방법

- 처음 문제를 보고 음수부터 양수까지 왔다갔다하는 x,y의 범위를 보며 겁먹지 말고 단순히 그래프 탐색이라는 방법으로 다가가야함
- 주인공이 어떻게 가던지 목적지에 도착을 하냐 못하냐만 알고 싶은 문제이므로 BFS탐색을 이용해 모든 루트를 탐색해본다.
- 들고 다닐 수 있는 맥주는 총 20개이고 한개로 움직일 수 있는 거리는 50미터이므로, 총 1000미터를 기준으로 방문 예정인 편의점이 그보다 가깝게 있으면 계속 방문해보는 방식
- 다만 무한히 돌아다닐 순 없으므로 편의점에 방문표시를 해주어야 하는데 나의 경우는 문제에 나온 x,y의 범위가 5000이하라는 것을 이용하여 구조체에 넣어놓은 편의점의 위치정보 원본을 10만으로 바꾸어 주며 방문표시를 하였다. 

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N (100)

typedef struct {
	int x;
	int y;
}POS; 

typedef struct {
	int r;
	int c;
	int check;
}QUE;

QUE que[100 * 100 + 10];

int N;
POS pos[MAX_N + 2];


void Input_Data(void) {
	int i;
	scanf("%d", &N);
	for (i = 0; i < N + 2; i++) {
		scanf("%d %d", &pos[i].x, &pos[i].y);
	}
}

int wp, rp;


void push(int r, int c)
{
	que[wp].r = r; que[wp].c = c;
	wp++;
}
void pop()
{
	rp++;
}

QUE front()
{
	return que[rp];
}

int empty()
{
	return rp == wp;
}

int BFS() 
{
	//초기화
	wp = rp = 0;
	
	//초기 푸시
	push(pos[0].y, pos[0].x);

	while (!empty())
	{
		QUE cur = front();
		pop();
		for (int i = 1; i < N + 2; i++)
		{
			if (pos[i].y == 100000) continue; //방문 표시가 있다면 스킵
			if (abs(cur.r - pos[i].y) + abs(cur.c - pos[i].x) <= 1000) //맥주 20개로 최대 갈 수 있는 거리보다 가깝다면 방문 가능한 편의점임 
			{
				if (i == N + 1) return 1; //도착지라면 1 리턴
				push(pos[i].y, pos[i].x); //도착지가 아니라면 푸시로 다음 목적지 출발
				pos[i].y = 100000; //방문한 곳은 문제 범위보다 큰 값을 주어 표시 
			}

		}
	}
	return 0;

}


int main(void) {
	int sol = 0;
	int T, t;
	scanf("%d", &T);
	for (t = 0; t < T; t++) {
		Input_Data(); // 입력 받는 부분

		// 여기서 부터 작성


		// 출력 하는 부분
		
		if (BFS() == 1)
		{
			printf("happy\n");
		}
		else
		{
			printf("sad\n");
		}

	}
}