[백준/BOJ] #9205 맥주마시면서 걸어가기.python(파이썬)

문제 링크 / 출처

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

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

 

풀이

파이썬에서 pop()메서드를 사용하면 리스트의 가장 마지막 항목을 가져온다.

 

따라서, 락페스티벌을 시작점으로, 집을 도착점으로 하여 풀이를 진행하였다.

 

지점(편의점)을 방문할 경우 맥주의 수가 초기화 되므로, 두 지점 사이의 거리가 1000m이하일 경우 이동가능하다.

 

따라서 각지점별로 이동가능 여부를 판단해 문제를 해결하였다.

 

1. 출발점과 도착점의 좌표를 설정한다.
2. 시작점을 다음 방문지점 스택에 추가한다.
3. 방문했던 지점을 체크하지 않으면 무한루프를 돌게 되므로 체크할 리스트를 생성한다.
4. 다음 방문지점 스택에서 현재 방문하는 지점을 하나씩 가져온다.
5. 현재 지점과 다른모든 지점을 비교했을 때, 거리가 1000m이하이고 방문한 적이 없을 경우 이동가능하므로, 다음 방문지점 스택에 추가하였다.
6. 5번을 수행하면서 도착점으로 이동이 가능할 경우 happy를 반환하였다.
7. 가능한 모든 지점을 방문했을 때에도 도착점에 도달하지 못할 경우 sad 반환

 

코드

def beer(path):

    start = path.pop()    # 시작점 좌표를 가져옴
    end = path[0]         # 도착점의 좌표를 가져옴
    next_store = [start]  # 시작점을 다음 방문지점으로 지정
    visited_store = []    # 한번 방문한 편의점을 다시 오지 않기 위해 리스트 생성

    while next_store:
        store = next_store.pop()        # 현재 방문하는 지점을 가져옴
        visited_store.append(store)     # 방문한 지점을 리스트에 추가  

        for i in path:
            if (abs(store[0] - i[0]) + abs(store[1] - i[1]) <= 1000) and (i not in visited_store):
                # 다음 지점과의 거리가 1000이하이고, 방문한 적이 없을 때
                next_store.append(i)    # 방문할 지점리스트에 추가

                if i == end:            # 다음 지점이 도착점일 때 happy반환
                    return 'happy'

    return 'sad'                        # 도착점에 도달하지 못할 때


T = int(input())
for _ in range(T):
    N = int(input())
    path = []
    for _ in range(N + 2):
        path.append(list(map(int, input().split())))
    print(beer(path))