9205 맥주 마시면서 걸어가기

#include <stdio.h>
#include <vector>
#include <utility>
#include <math.h>
#include <queue>
#include <string.h>
 
using namespace std;
 
int dist[105][105] = { 0 };
 
void bfs(int n) {
    queue<int> q;
 
    int cur = 0;
    int chk[105] = { 0 };
 
    chk[cur] = 1;
    q.push(cur);
 
    while (!q.empty()) {
        cur = q.front();
        q.pop();
        
        if (cur == n + 1) {
            printf("happy\n");
            return;
        }
 
        for (int i = 0; i < n + 2; i++) {
            if (chk[i] == 1 || dist[cur][i]>1000)
                continue;
            chk[i] = 1;
            q.push(i);
        }
    }
    printf("sad\n");
    return;
}
 
int main() {
    int t;
    scanf("%d", &t);
 
    while (t--) {
        int n;
        scanf("%d", &n);
 
        vector<pair<int, int> > xy(n + 3);        
 
        for (int i = 0; i < n + 2; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
 
            xy[i].first = x;
            xy[i].second = y;
        }
 
        // 거리 만들기
        memset(dist, 0, sizeof(dist));
        for (int i = 0; i < n + 1; i++) {
            for (int j = i + 1; j < n + 2; j++) {
                int len = abs(xy[i].first - xy[j].first)
                    + abs(xy[i].second - xy[j].second);
                dist[i][j] = len;
                dist[j][i] = len;
            }
        }
 
        bfs(n);
    }
}

간단한 문제였다.

각 노드들의 거리를 구하고,

시작 노드 idx=0, 끝 노드 idx=n+1 로 둔 다음에 bfs를 돌렸다.

생각보다 간단했다.

조금만 머리를 굴리면 됐다