알고리즘/너비 우선 탐색(bfs)
9205-백준-맥주 마시면서 걸어가기
easysheep
2023. 2. 7. 23:04
1. 문제 출처
https://www.acmicpc.net/problem/9205
9205번: 맥주 마시면서 걸어가기
송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다.
www.acmicpc.net
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)