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

1. 문제 출처

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

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

2. 풀이

# 테스트 테이스의 개수
t = int(input())
# 편의점 좌표 입력받는 함수
get_coordinate = (lambda : list(map(int,input().split())) )
# 길이 구하는 함수
get_legth = (lambda start , end : abs(start[0]-end[0])+abs(start[1]-end[1]))
# 결과 저장하는 리스트
result_list = []


for _ in range(t):
    # 편의점의 개수
    n = int(input())
    
    # 사용할 변수 초가화
    start = get_coordinate()
    queue = [start]
    con_list = []
    result = "sad"
    
    # 편의점 좌표 받기
    for _ in range(n):
        con_list.append(get_coordinate())
    # 페스티벌 좌표 받기
    end = get_coordinate()
    
    # 방문 여부
    visted = [-1 for i in range(n)]
    
    # queue가 빌동안 반복
    while queue:
        start = queue.pop(0)
        length = get_legth(start ,end)
        # 길이가 맥주 다 마시기 전까지 된다면 happy 로 하고 while문 종료
        if length <= 1000:
            result = "happy"
            break
        
        # 편의점 개수 만큼 반복
        for idx in range(n):
            # 만약 방문하지 않음 편의점일 경우
            if visted[idx] == -1:
                length = get_legth(start ,con_list[idx])
                # 현재 좌표에서 방문이 가능한지 구한다.
                if length <= 1000:
                    visted[idx] = 1
                    queue.append(con_list[idx])
    # 결과 리스트에 나온 결과를 추가한다.
    result_list.append(result)

# 결과 출력
for result in result_list:
    print(result)

그래프 탐색 + BFS(너비 우선 탐색)