문제링크: https://www.acmicpc.net/problem/9205

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나면 "sad"를 출력한다.

풀이

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

int visited[102] = { 0, };
std::vector<int> g[102];

void dfs(int start) {
	visited[start] = true;

	for (int i = 0; i < g[start].size(); i++) {
		int next = g[start][i];

		if (!visited[next]) {
			dfs(next);
		}
	}
}

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

	int t; std::cin >> t;

	for (int tc = 0; tc < t; tc++) {
		for (int i = 0; i < 102; i++) {
			g[i].clear();
		}

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

		int n; std::cin >> n;
		std::vector<std::pair<int, int>> v(n + 2);

		for (int i = 0; i < n + 2; i++) {
			std::cin >> v[i].first >> v[i].second;
		}
		
		for (int i = 0; i < n + 2; i++) {
			for (int j = i + 1; j < n + 2; j++) {
				if (abs(v[i].first - v[j].first) + abs(v[i].second - v[j].second) <= 1000) {
					g[i].push_back(j);
					g[j].push_back(i);
				}
			}
		}

		dfs(0);

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

	return 0;
}

깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

자료구조 수업에서 그래프를 배우고 난 후 탐색법을 배우는데, 개인적으로 어려워하는 알고리즘이다.

그래프를 만들어서 방문되지 않은 곳을 탐색해 방문 했으면 happy를 출력하고 아니면 sad를 출력하면 되는 간단한 dfs문제였다.

노트

이제부터는 가능한 dfs, bfs 위주로 문제를 풀어보고자 한다.
PS 문제를 풀 때의 기본이 되기도 하고, 언제까지 어렵고 귀찮다고 피할 수는 없기 때문이다.