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

문제 링크

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

문제 코드

from collections import deque

T = int(input())


for test in range(T):
    conv = int(input())

    start_x, start_y = list(map(int,input().split()))

    conv_list = []
    for c in range(conv):
        tmp_conv = list(map(int,input().split()))
        conv_list.append(tmp_conv)

    visited = [0]*(conv+1)

    end_x, end_y = list(map(int,input().split()))

    conv_list.append([end_x,end_y])
    que = deque()

    que.append([start_x,start_y])

    end_checker = False
    while len(que)>0:
        now_x,now_y = que.popleft()

        if now_x == end_x and now_y == end_y:
            end_checker = True
            break
        for i in range(conv+1):
            if visited[i] ==0 and abs(now_x - conv_list[i][0]) + abs(now_y - conv_list[i][1]) <= 1000 :
                que.append([conv_list[i][0],conv_list[i][1]])
                visited[i] = 1

    if end_checker:
        print('happy')
    else:
        print('sad')

문제 풀이

• 처음 위치를 큐에 넣음
• end 위치도 conv_list에 같이 넣음
• 현재 위치에서 아직 방문하지 않았거나, 거리가 1000이하인 편의점들을 큐에 넣음
• end위치에 도착하면 break하고 출력