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

1. 풀이

(1) 답은 목적지까지 도달이 가능한지 안한지만 알면 된다.

(2) 오직 편의점에서만 충전이된다. 즉 현재위치에서 편의점까지의 거리가 50*20(=1000) 맨하탄 거리 이내이면 이동이 가능하다.

(3) 즉 현재위치와 1000맨하탄 거리 이내에 있는 편의점 사이에 (가중치가 일정한) 간선이 있는 그래프로 문제를 해석할수 있다.

(4) 가중치가 일정한 그래프의 최소거리구하기 -> bfs

​

2. 소스코드

from collections import deque

def manhaten(a,b,c,d):
    return abs(a-c)+abs(b-d)


T=int(input())
for t in range(T):
    ans = "sad"
    N=int(input())
    homeX,homeY=map(int,input().split())
    convL = []
    visited=[0 for i in range(N)]
    for i in range(N):
        convL.append(list(map(int,input().split())))

    toX,toY=map(int,input().split())
    q=deque([[homeX,homeY]])
    while(q):
        temp=q.popleft()
        r=temp[0]
        c=temp[1]
        # 목적지까지 가능하면 끝남
        if manhaten(r,c,toX,toY)<=1000:
            ans="happy"
            break
        for i in range(N):
            if visited[i]==0 and manhaten(convL[i][0],convL[i][1],r,c)<=1000:
                q.append([convL[i][0],convL[i][1]])
                visited[i]=1
    print(ans)