[9205] 맥주 마시면서 걸어가기 - BFS ★☆☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/9205

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

---

[ 문제 접근 ]

 

- 플로이드 문제라고 태그 되어 있길래 플로이드로 풀려고 아무리 생각해봐도 플로이드 문제가 아닌거 같아서, 봤더니 DFS / BFS 문제 였다.

 

다른 사람들 풀이를 보니 플로이드 와샬로 푸는 것도 봤다.

 

---

[ 최종 코드 ]

 

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


using std::cout; using std::cin;
using std::vector;

vector<std::pair<int, int>> graph;

int t, n;
bool visited[101];

void bfs() {
	std::queue<std::pair<int, int>> que;

	int start_x = graph.begin()->first;
	int start_y = graph.begin()->second;

	que.push({ start_x,start_y });

	visited[0] = true;

	while(!que.empty()) {
		std::pair<int, int> cur = que.front();
		que.pop();

		  // graph[n+1] 은 목적지인 페스티벌 장소 좌표 pair(x,y)
		if (cur.first == graph[n + 1].first && cur.second == graph[n + 1].second) { 
			cout << "happy" << '\n';
			return;
		}
		for (int i = 1; i <= n + 1; i++) {
			if (visited[i] ) continue; // 이미 방문 했으면 
			int distance = std::abs(graph[i].first - cur.first) + std::abs(graph[i].second - cur.second);
			if (distance <= 1000) { // 거리가 1000 이하 장소만 추가.
				que.push(graph[i]);
				visited[i] = true;
			}
		}
	}

}
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> t;
	while (t--) {
		cin >> n;
		int m = n + 2;
		while (m--) {
			int x, y;
			cin >> x >> y;
			graph.push_back({ x,y });
		}
		bfs();

		std::fill_n(visited, n + 2, false); // visited 배열 초기화.
		graph.clear(); // 그래프 초기화
	}

	
	return 0;
}

---

[ Key Point ]

 

👉 항상  BFS 를 여러번 돌릴때는 Visited 배열 초기화는 잊지말자!!  -> 찾느라 애 많이 먹었다.

std::fill_n(visited, n + 2, false); // visited 배열 초기화.
graph.clear(); // 그래프 초기화

여기서는 입력으로 주어지는 graph도 바뀌기 때문에 graph 역시 초기화 해줘야한다.

 

 

👉 출발 지점은 ( 0,0 ) 이 아닐 수도 있다.

 

=> 이거 때문에 1시간은 족히 쓴 듯하다. 나는 당연히 ( 0 , 0 ) 에서 시작하는 줄 알고 

que.push({ 0,0 });

 만 해줬는데 아래 처럼 출발 노드를 그래프에서 꺼냈어야 했다.

 

int start_x = graph.begin()->first;
int start_y = graph.begin()->second;

que.push({ start_x,start_y });

 

---

[ 알게 된 점 ]

 

문제 덕분에 '맨해튼 거리'라는 개념을 처음 알게 되었다.

맨해튼 거리는 두 좌표 사이의 거리를 'x 좌표간의 거리' + 'y 좌표간의 거리'로 표현하는 방법이다. 

 

https://ko.wikipedia.org/wiki/%EB%A7%A8%ED%95%B4%ED%8A%BC_%EA%B1%B0%EB%A6%AC

---

[ 다른 사람 풀이 ]

 

ref :: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=fbfbf1&logNo=222264183558