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

문제

일정 거리에 따라 맥주를 마시면서 도착지점에 가려고 할 때,
갈 수 있는지 없는지 알아내자!

생각

도착 할 수 있는지 없는지 그냥 구하는 거니까 BFS/DFS 상관없겠구나!
(+ 다익스트라, 플로이드 와샬 등 다양하게도 풀 수 있더라)

메모리 초과 아이디어

나는 대부분 미로 탈출, 퍼져나가기, 갈 수 있는 길 문제 등
한 칸 한 칸 갈 수 있는지를 보거나, 노드 노드 정보를 받는 문제가 익숙했어서

이것도 처음엔
50미터에 한 병씩, 좌표는 미터 단위로 주어진다. 길래
1미터에 0.02병 씩 소모하며 한칸 한칸 가는 코드를 짰다..!

queue<pair<int, pair<int, int>>> q; //가진 맥주 정보, 좌표 x, 좌표 y

void buy(int beer, int x, int y) { //현재 맥주양, 새로 이동한 좌표 x, y
	if (편의점이면) {
              q.push(make_pair(1000, make_pair(x, y)));
        }else{
              q.push(make_pair(beer-1, make_pair(x, y)));
        }
}

거의 좌표 모두를 다 큐에 넣어주니 터질 수 밖에.. 하하하ㅏㅎ하

수정후

한칸 한칸 좌표 이동해서 가는 게 아니라
위치 위치 사이가 갈 수 있는지 보고 갈 수 있으면 거기로 다녀오기!

pair<int, int> p[105]; //주어지는 위치(point) 좌표를 저장하기 위해
//p[0] 상근이네 집, p[1~n] 편의점, p[n+1] 페스티벌 좌표

int visited[105]; //이미 탐색한 곳 안 가려고 표시

//p 배열 두 곳 인덱스가 들어올 때, 거리가 이동 가능하면 true반환
bool canGo(int sv, int dv) {
	if (abs(p[sv].first - p[dv].first) + abs(p[sv].second - p[dv].second) <= 1000) {
		return true;
	}
	else {
		return false;
	}
}


        //////
        if (canGo(nowV, i)) {
                visited[i] = 1;
                //dfs(i); 또는
                //q.push(i);
        }
        //////

아 좌표가 아니라 위치간에 이동을 해야하는구나! 라고 맨 처음 알았을 때는

인접 그래프를 만들고 (vector adj[105])
맨 처음 한 번 모든 위치(p)를 다 돌면서
어떤 위치(p[i])에서 위치(p[j])로 갈 수 있다면
adj[i]에 j을 달아주는 방법을 생각했었는데

이럴필요도 없이 그냥 탐색하면서 그때 그때 구하고
인덱스를 계속 타고 들어가거나 큐에 추가해주면 된다는걸 알게됬당

(+신기하게 BFS랑 DFS 둘 다 메모리랑 걸린 시간이 같았다!!)

코드

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

using namespace std;

int t, n;

pair<int, int> p[105]; //주어지는 위치(point) 좌표를 저장하기 위해
//p[0] 상근이네 집, p[1~n] 편의점, p[n+1] 페스티벌 좌표

int visited[105]; //이미 탐색한 곳 안 가려고 표시

queue<int> q;

bool canGo(int sv, int dv) {
	if (abs(p[sv].first - p[dv].first) + abs(p[sv].second - p[dv].second) <= 1000) {
		return true;
	}
	else {
		return false;
	}
}

void bfs(int sv) {
	q.push(sv);

	while (!q.empty()){
		int nowV = q.front();
		q.pop();
		for (int i = 1; i < n + 2; i++) {
			if (visited[i] == 0) {
				if (canGo(nowV, i)) {
					visited[i] = 1;
					q.push(i);
				}
			}
		}
	}
}

void dfs(int nowV) {
	for (int i = 1; i < n + 2; i++) {
		if (visited[i] == 0) {
			if (canGo(nowV, i)) {
				visited[i] = 1;
				dfs(i);
			}
		}
	}
}

int main() {

	cin >> t;

	for (int i = 0; i < t; i++) {
		cin >> n;

		for (int j = 0; j < n + 2; j++) {
			cin >> p[j].first >> p[j].second;
		}

		visited[0] = 1;
		//bfs(0);
		dfs(0);

		if (visited[n + 1] == 1) {
			cout << "happy\n";
		}
		else {
			cout << "sad\n";
		}

		memset(visited, 0, sizeof(visited));
	}

	return 0;
}