[백준] 9205. 맥주 마시면서 걸어가기

백준 문제 풀이

 

[백준] 9205. 맥주 마시면서 걸어가기

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

 

---

문제 해석 & 접근 방법

출발지에서 50m씩 움직일 때마다 맥주 한 병이 필요하다. 맥주는 총 20개를 들고 있을 수 있고, 편의점에 도착할 경우에는 맥주가 20개로 리필된다.

출발지, 편의점들, 도착지의 좌표가 주어질 때 맥주가 다 떨어지지 않고 도착할 수 있는지 여부를 구하는 문제이다.

 

처음에는 BFS로 풀려고 접근했지만 플로이드 워셜 알고리즘을 이용하면 문제가 간단해질 것 같아 해당 알고리즘을 이용해 풀었다.

 

풀이

플로이드 워셜 알고리즘을 사용하기 위해서는 모든 점에 대해서 갈 수 있는지 여부를 저장하고, 이를 개선해 나가야 한다.

따라서 변수를 다음과 같이 설정해 주었다.

vector<pair<int, int>> lists;		// 출발지, 편의점들, 도착지의 좌표를 저장할 배열
bool is_reachable[103][103];		// i번째 점에서 j번째 점을 갈 수 있는지를 저장할 배열

lists에 출발지, 편의점들, 도착지의 좌표를 pair로 저장했다.
그 후 is_reachable에는 i번째 점에서 j번째 점을 갈 수 있는지 여부를 저장할 것이다.

is_reachable은 다음과 같은 구조이다

 

lists에 입력을 받고 난 뒤, 플로이드 워셜 알고리즘을 이용하기 위해 is_reachable을 채워준다.

		for (int x = 0; x < num_of_convenience_store + 2; x++)
		{
			for (int y = 0; y < num_of_convenience_store + 2; y++)
			{
				if (x == y) {
					is_reachable[x][y] = true;
				}
				else {
					int value_x_difference = lists[x].first - lists[y].first;
					if (value_x_difference < 0) {
						value_x_difference *= -1;
					}

					int value_y_difference = lists[x].second - lists[y].second;
					if (value_y_difference < 0) {
						value_y_difference *= -1;
					}

					if (value_x_difference + value_y_difference <= 1000) {
						is_reachable[x][y] = true;
					}
					else {
						is_reachable[x][y] = false;
					}
				}
			}
		}

이 때에는 어떤 점을 건너지 않고, 바로 연결된 경우에만 연결된 것으로 본다. 50m를 움직일 때마다 맥주 한 병이 필요하고, 맥주는 20개를 가지고 갈 수 있으므로 거리가 1000m이하일 때에 연결되어 있음을 알 수 있다.

 

0 0
1000 0
2000 1000
2000 2000

위와 같은 정보로 판을 채우면 다음과 같은 상태가 된다.

 

이제 플로이드 워셜 알고리즘을 이용한다.

void FloydWarshall() {
	// 플로이드 워셜 알고리즘을 이용해서 도착 가능성을 업데이트한다
	int lists_size = lists.size();
	for (int point = 0; point < lists_size; point++) {
		for (int i = 0; i < lists_size; i++) {
			for (int j = 0; j < lists_size; j++) {
				if (is_reachable[i][j] == false && is_reachable[i][point] == true && is_reachable[point][j] == true) {
					is_reachable[i][j] = true;
				}
			}
		}
	}
}

i번째 점에서 j번째 점으로 가기 위해서 point를 거쳤을 때, true가 되는지 확인하는 것이다. 만약 i번째 점에서 point점으로 가는 것이 true이고 point점에서 j로 가는 것이 true일 경우 그렇게 건너 가면 i번째 점에서 j번째 점으로 가는 것도 가능하므로 그런 경우를 lists안에 모든 점들을 하나씩 point로 하면서 계산해 본다.

 

계산이 끝나고 나면, is_reachable[출발지][도착지]가 true인지 false인지의 여부에 따라 "happy", "sad"를 출력하면 된다.

		// 3. is_reachable[0][num_of_convenience_store+1]값에 따라 결과가 결정된다./
		if (is_reachable[0][num_of_convenience_store + 1] == true) {
			cout << "happy";
		}
		else {
			cout << "sad";
		}
		cout << "\n";

 

++ 여러 테스트 케이스를 계산하는 것이므로 lists에 대한 초기화도 잊지 말자!

 

전체 소스코드 (Github)

GitHub - yarncha/baekjoon: yarncha's Baekjoon Algorithm Problem Solving😊