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

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

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

 

문제접근을 하는데 어려움을 겪었습니다.

처음에 가진 생각은 가장 이동경로내에 여러개의 편의점이 있으면 어디를 선택할까와 같은 생각을 했지만, 다시 생각해보니 무의미했습니다. yes, no로 도달할 수 있는지만 판단하면 되었기 때문입니다. 그렇기 때문에 모든 편의점을 탐색하며 도달할 수 있는지 여부만 판단했습니다.

 

bfs알고리즘을 사용해서 방문여부를 판단했습니다.

주의 하셔야 할 점은  두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리) 입니다.

문제를 꼼꼼히 읽는 습관을 가져야 합니다.

 

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std;
int t = 0, n = 0;
int arr[101][2] = { 0 };
int starting_x, starting_y, destination_x, destination_y;
bool visited[101];
int que[1000000][2] = { 0 };
int started = 0, ended = 0;

void bfs() {
	que[ended][0] = starting_y;
	que[ended++][1] = starting_x;

	while (started != ended) {
		int y = que[started][0];
		int x = que[started++][1];

		for (int i = 0; i <= n; i++) {
			if (!visited[i]) {
				int len_x = min(abs(x - arr[i][1]), abs(arr[i][1] - x));
				int len_y = min(abs(y - arr[i][0]), abs(arr[i][0] - y));
				double len_total = len_x + len_y;
				if (len_total <= 1000)
				{
					visited[i] = 1;
					que[ended][0] = arr[i][0];
					que[ended++][1] = arr[i][1];
				}
				
			}
		}
	}

}
int main() {
	cin >> t;

	while (t--) {
		cin >> n;
		cin >> starting_x >> starting_y;
		for (int i = 0; i < n; i++)
			cin >> arr[i][1] >> arr[i][0];
		cin >> arr[n][1] >> arr[n][0];

		memset(visited, 0, sizeof(visited));
		started = 0, ended = 0;

		bfs();
		if (visited[n])
			cout << "happy" << endl;
		else
			cout << "sad" << endl;
	}


}