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

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

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

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

def bfs(graph):
    q = deque()
    q.append(0)
    end = len(graph) - 1
    visit = [-1 for _ in range(len(graph))]
    visit[0] = 0
    while q:
        cur = q.popleft()
        if cur == end:
            return True
        for adj in graph[cur]:
            if visit[adj] != -1:
                continue
            visit[adj] = visit[cur] + 1
            q.append(adj)
    return False

t = int(input())
answer = ''

for tc in range(1, t + 1):
    n = int(input())
    p = [tuple(map(int, input().split())) for _ in range(n + 2)]
    linked_list = [list() for _ in range(n + 2)]
    for i in range(0, n + 2):
        for j in range(i + 1, n + 2):
            x = abs(p[i][0] - p[j][0])
            y = abs(p[i][1] - p[j][1])
            dist = x + y
            if dist <= 1000:
                linked_list[i].append(j)
                linked_list[j].append(i)
    result = bfs(linked_list)
    answer += "happy\n" if result else "sad\n"
print(answer)

난이도 실버 5인 BFS 문제이다.

집, 편의점, 목적지를 각각 vertex로 두고 그 사이를 edge라고 두고 집에서 목적지까지 갈수 있는지 확인하면 된다. 목적지까지 탐색하기 위해 그래프를 만들고 그래프 탐색 알고리즘을 적용하면 된다.

우선 그래프를 만들기 위해 edge부터 찾아보자. 모든 vertex 간의 맨하탄 거리가 1000m이하인지 확인하면 된다. 맥주 20병을 최대로 가지고 다닐수 있고 한병당 50m를 갈수 있으니 최대로 갈수 있는 거리가 1000m이다. vertex는 최대 102개이므로(집과 목적지까지 합쳤을 때) edge를 구하는 시간 복잡도(O(n^2))는 크지 않다.

모든 edge를 찾아서 graph를 구했으면 시작점을 0으로 두고 마지막점까지 갈수 있는지 파악하면 된다. bfs, dfs, dijkstra, floyd warshall 등을 사용하면 되는데 나는 bfs를 사용했다. 갈수있는지만 파악하면 되므로 도착지에 다다르면 true값을 리턴했다.

마지막으로 bfs의 결과에 따라 값을 달리해서 answer에 더해주면 된다.