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

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

from collections import deque

all = int(input())
answer = []
for _ in range(all):

    a = int(input())

    cvs = deque() # 편의점
    h_x, h_y = tuple(map(int, input().split()))
    for _ in range(a + 1): # 목적지 까지 구해야하기 때문에
            k = tuple(map(int, input().split()))
            cvs.append(k)
    cnt = 0
    x_rst = 0
    y_rst = 0
    que = deque() # 인접 노드 큐
    cvs_check = [0 for _ in range(a)] + [1] # 목적지 인지 아닌지 판단하기 위해 마지막에 1 추가
    cvs_check = deque(cvs_check)
    check = True

    while check == True :
        if cnt == 0:
            x_rst = h_x
            y_rst = h_y
        else:
            if len(que) == 0:
                answer.append("sad")
                check = False
                break
            x_rst, y_rst = que.popleft()
        for _ in range(len(cvs)):
            x, y = cvs[0]
            dis = abs(x - x_rst) + abs(y - y_rst)
            if dis <= 1000:
                que.append(cvs.popleft())
                target = cvs_check.popleft()
                if target == 1:
                    answer.append('happy')
                    check = False
                    break
                cnt += 1
            else:
                cvs.rotate(-1)
                cvs_check.rotate(-1)
                cnt += 1

for i in answer:
    print(i)

이틀동안 나를 괴롭힌 문제.

 

| 알고리즘

대충 요약하자면 처음에만 집 주소와 cvs에 있는 요소를 모두 계산 후, 1000이하 되는 것만 큐에 집어 넣는다. 그 다음 부터는

큐에 들어간 것들을 하나씩 popleft 해주면서 그것의 좌표를 x_rst, y_rst에 넣고 남은 cvs에 있는 편의점 및 목적지를 계산해 1000이하 되는 것을 큐에 넣는다. 이 때, cvs_check도 같이 popleft해줘야 일치 시킬 수 있다.  만약 1000이하가 아니라면 다음 좌표를 계산하기 위해서 rotate를 시켜준다. 이 때, 목적지를 알기위한 cvs_check도 같이 로테이트 시켜준다. 만약에 큐가 비면 다음으로 갈 곳이 없다는 것으로 'sad' 를 말하고 check를 False로 바꿔주어 while문을 탈출하고, happy를 추가하며 check를 False로 바꾸어준다.

 

| 얻어간 것

완벽한 bfs를 사용한 것은 아니지만 대충 그래프 탐색의 개념으로 문제를 풀었고, True와 False를 사용하여 세마포어 형식으로 while문을 제어 해보았다. 그리고 abs()함수는 절댓값 함수이다. 그리고 덱은 사랑이다.