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

문제 링크

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

구현 방식

• bfs로 풀어주었다
• 초기 맥주 20개, 50미터를 가려면 맥주 한 개를 마셔야하므로, src 또는 mid에서 출발하여 다른 mid 또는 dest로 가기 위해선 그 사이의 거리가 1000미터 이하여야 한다
• node는 pair<int, int> 형식, visited는 1차원 boolean type 배열로 설정하고 bfs를 수행해주었다

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define MAX 100

int N;
pair<int, int> src;
pair<int, int> mid[MAX];
pair<int, int> dest;
bool visited[MAX];

void bfs(){
    queue<pair<int, int>> Q; Q.push({src.first, src.second});

    while (!Q.empty()){
        int x = Q.front().first; int y = Q.front().second; Q.pop();

        if (abs(x-dest.first)+abs(y-dest.second) <= 1000){
            cout << "happy"; return;
        }
        else{
            for(int i=0; i<N; i++){
                if (!visited[i]){
                    int nx = mid[i].first; int ny = mid[i].second;
                    if (abs(x-nx)+abs(y-ny) <= 1000){
                        Q.push({nx, ny});
                        visited[i] = true;
                    }
                }
            }
        }
    }
    cout << "sad"; return;
}

int main() {
    int T; cin >> T;
    for (int t=0; t<T; t++){
        cin >> N;
        cin >> src.first >> src.second;
        for (int n=0; n<N; n++){
            cin >> mid[n].first >> mid[n].second;
        }
        cin >> dest.first >> dest.second;
        
        for (int i=0; i<MAX; i++){
            visited[i] = false;
        }
        bfs();
        cout << "\n";
    }

    return 0;
}

• cpp에서 좀 헤맸는데.. 출력 할 때 개행문자 안넣어서 계속 틀리고 있었음

import sys
from collections import deque
input = sys.stdin.readline

def bfs():
    queue = deque([]); queue.append((src[0], src[1]))
    visit = [False for _ in range(N)] #편의점들

    while queue:
        x, y = queue.popleft()
        if abs(x - dest[0])+abs(y-dest[1]) <= 1000:
            print("happy"); return
        else:
            for i in range(N):
                if not visit[i]:
                    nx, ny = mid[i]
                    if abs(x-nx)+abs(y-ny) <= 1000:
                        queue.append((nx, ny))
                        visit[i] = True
    print("sad"); return


T = int(input()[:-1])
for t in range(T):
    N = int(input()[:-1])

    src = list(map(int, input()[:-1].split()))
    mid = []
    for n in range(N): mid.append(list(map(int, input()[:-1].split())))
    dest = list(map(int, input()[:-1].split()))
    bfs()