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

https://www.acmicpc.net/problem/9205

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

<문제>

pair<int,int>로 입력받고, i < j를 만족하는 모든 (i, j)에 대해서, 맨해튼 거리에 따라 양방향 인접 리스트를 생성해준다.

시작도, 도착도아닌 정점 n개와, 시작과 도착 정점 한 개씩 총 n+2번 입력을 받아야 하며,

편의상 정점의 번호는 1부터 n+2까지로 생각하고 인접리스트를 구성해주었다.

 

인접 리스트를 잘 만들어 준다면, 실제로 탐색하는 부분은 어렵지 않다. bfs든 dfs든 모든 정점을 방문해보고,

탐색이 종료된 후에 [n+2]를 방문했는지에 따라서 happy나 sad를 출력하면 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[105];
pair<int, int> p[105];
int t, n, sy, sx, ey, ex;
bool visited[105];
void dfs(int cur) {
    visited[cur] = true;
    for (auto& next : adj[cur])
        if (visited[next] == false) dfs(next);
}
int main(void) {
    int i, j;
    cin >> t;
    while (t--) {
        cin >> n;
        for (i = 0; i < n + 2; i++) cin >> p[i].first >> p[i].second;
        for (i = 0; i <= 104; i++) adj[i].clear();
        for (i = 0; i < n + 1; i++) {
            for (j = i + 1; j < n + 2; j++) {
                int dist = abs(p[i].first - p[j].first) +
                           abs(p[i].second - p[j].second);
                if (0 < dist && dist <= 1000) {
                    adj[i + 1].push_back(j + 1);
                    adj[j + 1].push_back(i + 1);
                }
            }
        }
        memset(visited, 0, sizeof(visited));
        dfs(1);
        visited[n + 2] ? cout << "happy\n" : cout << "sad\n";
    }
    return 0;
}