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

www.acmicpc.net/problem/9205

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

아... 이 문제도 3시간 안에 푸는 문제 중 하나였는데,,,, ㅜㅜㅜㅜ 이게 bfs로 풀릴 거라곤 생각도 못했다. 

맨 처음에는 아 그리디네?? 왜 실버1이지?하면서 풀었다. 틀렸단다 아무리 봐도 틀릴 구석이 없는데,,,ㅜㅜ

맨 처음에 생각했던 건 입력받은 편의점 좌표들에 하나하나 옮겨가면서 이전 편의점과의 거리를 계산해 

1000이하면 다음으로 넘어가고, 1000보다 크면 sad를 출력하는 거였다.

 

틀린코드

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

using namespace std;

int main() {
	int tc;
	scanf("%d", &tc);
	for (int i = 0; i < tc; i++) {
		int n;
		scanf("%d", &n);

		int startx, starty;
		scanf("%d %d", &startx, &starty);

		vector<pair<int, int>> cu;
		for (int j = 0; j < n+1; j++) {
			int first, second;
			scanf("%d %d", &first, &second);
			cu.push_back({ first , second });
			//맨마지막 [n]은 축제좌표
		}
		///////입력준비 끝 ///////////
        
		int prevx = startx, prevy = starty;
		bool stop = false;

		for (int j = 0; j < n+1; j++) {
			int distance = abs(cu[i].first - prevx) + abs(cu[i].second - prevy);
			if (distance > 1000) {
				stop = true;
				break;
			}
			else prevx = cu[i].first, prevy = cu[i].second;
		}
		if (stop) printf("sad\n");
		else printf("happy\n");
	}
}

IDEA

왜 틀렸을까?? 검색게시판을 보고 깨달았다. 

편의점은 주어진 순서대로 가는 게 아닙니다 

...... 문제에서는 편의점이 주어진 순서대로 간다고 써있지않다. 그냥 예제가 주어진 순서대로 갈 수 있다보니 별 생각없이 그리디로 풀었던 거 같다.

주어진 순서대로가 아닌 그냥 갈  수 있는 편의점에 가면 되는 문제라면 bfs를 이용해 풀 수 있을 거 같다.

그래서 2차원 좌표를 설정해서 그 편의점의 위치를 표시해주려고 했는데 

편의점의 위치는 -32767부터 32767까지,,,, 2차원 좌표를 설정하기 싫어지는 음수가 나와ㅏ버린다.

그래서 다른 방식을 선택했다. 바로 입력받은 순서를 가지고 확인하는거다. 

 

cu라는 pair벡터에 편의점의 위치와 시작점 , 도착점의 위치를 저장한다.

cu[0] = 시작점x , 시작점 y 가 되고 

cu[1]  ~ cu [n] = 편의점의 x좌표 , 편의점의 y좌표 

cu[n+1] = 도착지점의 x좌표 , 도착지점의 y좌표가 된다. 

 

시작점을 뜻하는 인덱스 0을 큐에 집어넣어주고 방문처리를 해준다. 

이후 cu벡터의 크기만큼 for문을 돌며 i번째 인덱스가 가르키는 좌표와 현재 좌표의 차를 계산해

맥주 20 병 즉, 거리가 1000보다 작거나 같으면 큐에 넣어주고 방문 처리를 해준다. 

1000보다 크면 넘어가게 된다. 

그리고 나서 큐에서 꺼낸 인덱스가 n+1과 같다면, true를 반환해준다. 

while문이 끝났는데도 return이 안됐다는 건 도착지점에 갈 수 없단 뜻이므로 false를 반환해준다.  

 

✨문제를,,,,좀 더 잘 읽는,,,, 맘대로 해석하지 않는 사람이 됩시다,,,,✨

정말 알고리즘 풀 때 마다 고3이 된 기분,,,,

 

정답코드

#include <iostream>
#include<vector>
#include<queue>
using namespace std;

vector<pair<int, int>>cu;

bool bfs( int start ) {
	queue<int>q;
	bool visited[101] = { false };
	q.push(start);
	visited[start] = true;
	while (!q.empty()) {
		int pos = q.front();
		q.pop();
		if (pos == cu.size() - 1) return true;
		for (int i = 0; i < cu.size(); i++) {
			int distnace = abs(cu[i].first - cu[pos].first) + abs(cu[i].second - cu[pos].second);
			if (!visited[i] && distnace <= 1000) {
				q.push(i);
				visited[i] = true;
			}
		}
	}
	return false;
}

int main() {
	int tc;
	scanf("%d", &tc);
	for (int t=0; t < tc; t++) {
		int n;
		scanf("%d", &n);
		cu.clear();
		for (int i = 0; i < n + 2; i++) {
			int x, y;
			scanf("%d %d", &x, &y);
			cu.push_back({ x,y });
		}
		if (bfs(0)) printf("happy\n");
		else printf("sad\n");
	}
}