BOJ 9205 - 맥주 마시면서 걸어가기 링크
(2023.04.25 기준 G5)

문제

맥주 한 박스에는 맥주 20병이 들어 있고, 맥주 한 병당 최대 50미터까지 갈 수 있다.
그리고 n개의 편의점에서 맥주 한 박스를 다시 채울 수 있다.
집, 편의점 n개, 락 페스티벌의 좌표가 주어진다면 락 페스티벌에 갈 수 있는지 검사

알고리즘

n이 최대 100이므로 플로이드-워셜도 가능하고 BFS도 가능하다. 난 BFS를 쓰는 방법을 풀이하겠다.

풀이

모든 장소 쌍마다 맨해튼 거리를 계산하여 맥주 20병으로 갈 수 있는지 검사하자.
만약에 갈 수 있다면 그 장소 쌍을 양방향 간선으로 하여금 그래프에 추가하자.

그리고 완성된 그래프로 BFS를 돌리면 된다.
어찌됐든 갔던 곳은 또 갈 필요가 없기 때문에 방문 체크를 하면서 도달할 수 있는지 검사하면 되는 것이다.

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> pii;

double distance(pii a, pii b){ // 맨해튼 거리
    return abs(a.x - b.x) + abs(a.y - b.y);
}

void solve(){
    int n;
    cin >> n, n += 2; // 장소의 총 개수는 n + 2

    vector<pii> pos;
    for (int i = 0, x, y; i < n; i++) cin >> x >> y, pos.push_back({x, y});

    vector<int> graph[n];
    for (int i = 0; i < n - 1; i++) for (int j = i + 1; j < n; j++)
        if (distance(pos[i], pos[j]) / 50 <= 20) // 맥주 20병으로 갈 수 있는지 검사
            graph[i].push_back(j), graph[j].push_back(i);

    // 위에서 만든 그래프로 bfs를 돌려 락 페스티벌 장소인 n-1번에 도착하면 happy 출력
    deque<int> dq = {0};
    bool visited[n];
    visited[0] = true, fill(visited + 1, visited + n, false);
    while (!dq.empty()){
        int here = dq.front(); dq.pop_front();
        if (here == n - 1){
            cout << "happy\n";
            return;
        }
        for (int there: graph[here]) if (!visited[there]) dq.push_back(there), visited[there] = true;
    }
    cout << "sad\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) solve();
}

• Python

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

def distance(a, b): # 맨해튼 거리
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

for _ in range(int(input())):
    n = int(input()) + 2 # 장소의 총 개수는 n + 2
    pos = [tuple(map(int, input().split())) for _ in range(n)]

    graph = [[] for _ in range(n)]
    for i in range(n - 1):
        for j in range(1, n):
            if distance(pos[i], pos[j]) / 50 <= 20: # 맥주 20병으로 갈 수 있는지 검사
                graph[i].append(j)
                graph[j].append(i)

    # 위에서 만든 그래프로 bfs를 돌려 락 페스티벌 장소인 n-1번에 도착하면 happy 출력
    queue = deque([0])
    visited = [False] * n
    visited[0] = True
    while queue:
        here = queue.popleft()
        if here == n - 1:
            print('happy')
            break
        for there in graph[here]:
            if not visited[there]:
                queue.append(there)
                visited[there] = True
    else:
        print('sad')