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

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

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

문제

풀이

엥 이건 bfs/dfs 가 아닌가 하고 접근하다 하나하나씩 50m 갈 때마다 편의점을 찾거나 맥주 하나 감소시키고 맥주 개수 0 되면 return 하고 이리 저리 풀다가 아 bfs 네... 하고 깨달은 문제. 왜 bfs 냐. 페스티벌까지 최단거리로 가고 싶기 때문.

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

def beer(home, festival, stores, visited): 
    queue = deque([(home[0], home[1], 20)])  # 큐 초기화

    while queue: 
        x, y, num_beer = queue.popleft() # 집 좌표 x,y 와 남은 비어 개수

        if abs(x - festival[0]) + abs(y - festival[1]) <= 1000:
            print('happy')
            return
        
        # 편의점 방문 체크
        for i in range(len(stores)):
            storex, storey = stores[i]
            if not visited[i] and abs(x - storex) + abs(y - storey) <= 1000:
                queue.append((storex, storey, 20))
                visited[i] = True
    
    print('sad')
    return


t = int(input())

for _ in range(t):
    n = int(input()) # 편의점 개수
    visited = [False] * n # 편의점만 방문했는 지 확인

    home = list(map(int, input().split()))
    stores = [] #stores[0] 이 편의점 1번, stores[2]가 편의점 2번
    
    for i in range(n): 
        store = list(map(int, input().split()))
        stores.append(store)

    festival = list(map(int, input().split()))
    
    beer(home, festival, stores, visited)

📌 주의

• 일단 나는 상하좌우 문제에 너무 익숙해진 나머지, 이 친구도 -50, +50 하며 왔다갔다 시키고 있었는데, 그러면 편의점을 어떻게 찾지 하다가 ... 아

  50 * 20 = 1000 m 안에만 편의점이 있으면 큐에다가 편의점 위치를 넣고 편의점 visited 를 true 로 바꿔주면 되겠구나. 그리고 만일 현재 위치가 festival 로부터 1000 m 이하면, print('happy') 하고 리턴해주면 되겠구나.

• 그리고 처음에 visited 안해도 되지 않을까 해서 안했다가 무한루프에 빠져버려서 visited 가 필수였다는 사실을 깨달았다.
• 내가 계속 헷갈리는 것:

list = [[1,2],[3,4]]
for i in list:
	print (i) # [1,2][3,4]
for i in range(len(list)):
	x,y = list[i] #x는 1 y는 2가 되었다가 3, 4 가 된다.