[백준 9205] 맥주 마시면서 걸어가기 (C++) DFS, BFS 풀이

# 문제링크

www.acmicpc.net/problem/9205

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

이걸 첨에는 현재 좌표부터 1000m 거리 이내에 있으면 다 해보면 된다고 생각해서 DFS로 짰는데 시간초과가 났다. 사실 편의점의 갯수 n 이 100이니까 그냥 100개의 노드에서 DFS를 돌리면 시간초과는 당연한 결과다. 좌표값들을 정렬한다음에 우선순위로 하면 되지 않을까? 이런 생각도 했었는데, 잘못된 방법이었다. 

 

결론 먼저 말하면, BFS로 풀거나, DFS로 풀때는 이미 방문한 노드를 다시 방문하지 않으면 된다. 이미 해당 노드로 진행을 했는데 안됐으면, 다시 진행해 볼 필요가 없는 것이다. 근데 앞으로는 그냥 BFS로 푸는 게 좋을 것 같다.

 

최단거리,, 거리 이런거 나오면 BFS로 가는걸로... 화이팅! 아 그리고 오늘도 visited 배열 초기화 깜박했다. 

 

- 테케 여러 개 돌릴 때,,,, 배열 초기화 명심하기.... 

 

 

# 제출 코드 

 

// BFS

 

#include <cstdio>
#include <cstring>
#include <queue>
#define abs(x) (((x) > 0)? (x): -(x))
using namespace std;

int N;
struct ST {
	int x;
	int y;
};
ST store[100];
ST goal;
ST home;
bool visited[100];
// 편의점 없이 갈 수 있는 최대 거리 1,000m (50 m * 20)
bool Solve() {
	queue <pair<int, int>> q;
	q.push({ home.x, home.y }); // 시작

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (abs(x - goal.x) + abs(y - goal.y) <= 1000) return true;

		for (int i = 0; i < N; i++) {
			if (visited[i] == true)continue;
			int d = (abs(x - store[i].x) + abs(y - store[i].y));
			if (d <= 1000) {
				visited[i] = true;
				q.push({ store[i].x, store[i].y });
			}
		}
	}
	return false;
}
void Input() {
	scanf("%d", &N);
	scanf("%d %d", &home.x, &home.y);
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &store[i].x, &store[i].y);
	}
	scanf("%d %d", &goal.x, &goal.y);
}

int main() {
	// freopen("sample_input.txt", "r", stdin);
	int T;
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		Input();
		if (Solve()) printf("happy\n");
		else printf("sad\n");
		memset(visited, 0, sizeof(visited));
	}
}

 

 

// DFS

 

#include <cstdio>
#include <cstring>
#include <queue>
#define abs(x) (((x) > 0)? (x): -(x))
using namespace std;

int N;
struct ST {
	int x;
	int y;
};
ST store[100];
ST goal;
ST home;
bool visited[100];
// 편의점 없이 갈 수 있는 최대 거리 1,000m (50 m * 20)


bool DFS(int node, int x, int y) {
	if (abs(x - goal.x) + abs(y - goal.y) <=1000) return true; // 도착
	if (node == N)return false;

	for (int i = 0; i < N; i++) {
		if (visited[i] == true)continue;
		int d = (abs(x - store[i].x) + abs(y - store[i].y));
		if (d > 1000)continue;
		visited[i] = true;
		if(DFS(node + 1, store[i].x, store[i].y)) return true;
		// visited[i] = false; 해본 곳은 다시 해보지 않아도 됨.
	}
	return false;
}

void Input() {
	scanf("%d", &N);
	scanf("%d %d", &home.x, &home.y);
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &store[i].x, &store[i].y);
	}
	scanf("%d %d", &goal.x, &goal.y);
}

int main() {
	//freopen("sample_input.txt", "r", stdin);
	int T;
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		Input();
		if (DFS(0, home.x, home.y)) printf("happy\n");
		else printf("sad\n");
		memset(visited, 0, sizeof(visited));
	}
}

 

 

 

아래 결과가 BFS고 맨 위에 결과가 DFS이다. 시간이나 메모리 차이는 크게 나지 않았다.