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

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

from collections import deque

t = int(input()) # 테스트 개수

def bfs(x, y, graph):
    # 한 박스당 1000m 이동 가능(50*20)
    # 1000M 내로 편의점 / 목적지 도달 실패 ==> sad

    while graph:
        a, b = graph.popleft()

        if abs(x-a) + abs(y-b) >= 1000:
            print("sad")
            return False
        else:
            x, y = a, b
    
    print("happy")
    return True


# main
for _ in range(t):
    n = int(input()) # 맥주를 파는 편의점의 개수
    
    graph = deque()
    start_x, start_y = map(int, input().split()) # 집의 위치

    # 편의점 위치
    for _ in range(n+1):
        x, y = map(int, input().split())
        graph.append((x, y))

    bfs(start_x, start_y, graph)

코드를 이런식으로 짜놓고, visited를 설정하는 대신 편의점을 모두 방문하는 경우의 수만을 고려하며 작성하였다.

그러나 이렇게 짜게 되면 출발지와 모든 편의점과 목적지가 1000m 이내의 최단거리에 위치해 있을 때에만 적용이 가능한 코드이다.

편의점을 기준으로 bfs를 짜버렸다...에휴

편의점을 지나도, 안지나도 된다는 점을 생각하자!

visited 리스트를 어떻게 써야할지 감이 안왔었는데, 이렇게 구현을 해야겠다..

from collections import deque

def bfs():
    q = deque()
    q.append((home_x,home_y))
    while q:
        x,y = q.popleft()
        if abs(x-festival_x) + abs(y-festival_y) <= 1000:
            print('happy')
            return
        for i in range(n): #편의점들 확인
            if not visited[i]: #편의점을 방문하지 않았다면
                new_x,new_y = graph[i] #편의점의 좌표를 새로 뽑고
                if abs(x-new_x) + abs(y-new_y) <= 1000: #다음거리까지 갈 수 있다면
                    visited[i] = 1 #방문체크해주고
                    q.append((new_x,new_y)) #큐에 담아준다
    print('sad')
    return
#1번째 반복에서는 집 -> 편의점을 확인한다
#다음 편의점까지의 거리가 1000 이하면은 -> 50미터에 한병을 까재끼니까
#1000이하면 다음 편의점까지 무사히 갈 수 있다는 것

t = int(input())
for _ in range(t):
    n = int(input())
    home_x,home_y = map(int,input().split()) # 집 위치
    graph = []
    # 편의점 위치
    for _ in range(n):
        x,y = map(int,input().split())
        graph.append((x,y))
    festival_x,festival_y = map(int,input().split()) # 목적지 위치
    visited = [0 for _ in range(n+1)] # 방문 Q
    bfs()

생각보다 쉬웠는데.. 좀 더 집중해야겠다

갈 길이 매우 멀어보인다.. ㅠㅠ