백준 9205 맥주마시면서걸어가기 c++ // bfs, 출력시 "\n을 빼먹지마라.."

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

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

 

1. 의사코드

sy,sx,ey,ex : 시작점, 끝점 좌표저장

vector : 편의점의 좌표들 저장

vis[i] : i번 편의점의 방문여부 저장  = > 중복방문 안하도록

50*20==1000이므로 1000미터 이내를 인접노드로 본다!

if(거리 <=1000) -> 인접노드에 추가한다

 

2.bfs 복습(문어박사)

1. q초기값넣기, 초기화 등

2. cur값체크, !종료조건!

3.nxt값체크, 큐에넣기

 

3. 전체코드

#include <bits/stdc++.h>

using namespace std;

int t,n,sy,sx,ey,ex,cy,cx;
vector<pair<int, int>> v; //편의점들의 좌표저장
int vis[104];

string bfs() {
    queue<pair<int, int>> q;
    fill(vis, vis + 104, 0);

    q.push({ sy, sx });

    while (q.size()) {
        tie(cy,cx) = q.front(); q.pop();
        if (abs(cy - ey) + abs(cx - ex) <= 1000) return "happy\n";

        for (int i = 0; i < v.size(); ++i) {
            if (vis[i]) continue;
            int ny = v[i].first; int nx = v[i].second;
            if (abs(cy - ny) + abs(cx - nx) > 1000) continue;
            q.push({ ny,nx });
            vis[i] = 1;
        }
    }

    //큐가 다 비었는데 해피가아닌경우
    return "sad\n";
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    while (t--) {
        //1. 1000미터 이내->인접
        v.clear();

        cin >> n;

        cin >> sy >> sx;
        for (int i = 0; i < n; ++i) {
            int y, x;
            cin >> y >> x;
            v.push_back({ y,x });
        }
        cin >> ey >> ex;

        //bfs
        cout << bfs();
        
    }
    return 0;
}