Coding Test/BaekJoon_Python
백준 9205 <맥주 마시면서 걸어가기> Python
JunOnJuly
2023. 10. 28. 22:40
728x90
https://www.acmicpc.net/problem/9205
9205번: 맥주 마시면서 걸어가기
송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다.
www.acmicpc.net
전형적인 그래프 탐색 문제입니다. 다만 DFS 로 풀었다 시간초과가 발생해서 BFS 로 풀었습니다.
from collections import deque
def solution(n, field):
# 맵 정리
start, field = field[0], field[1:]
# BFS 로 풀거
que = deque([start])
# 방문 기록
visited = [1 for _ in range(n+1)]
while True:
# 이동 가능 위치가 없으면
if not que:
return 'sad'
# 현재 위치
now = que.popleft()
# 도착하면
if not visited[-1]:
return 'happy'
for idx, store in enumerate(field):
# 이동 가능 거리에 있고 방문한 적 없으면
if (cal_distance(now, store) <= 1000) and \
(visited[idx]):
que.append(store)
visited[idx] = 0
# 거리 계산
def cal_distance(idx1, idx2):
return abs(idx1[0] - idx2[0]) + abs(idx1[1] - idx2[1])
t = int(input())
for _ in range(t):
n = int(input())
field = [list(map(int, input().split())) for _ in range(n+2)]
print(solution(n, field))
728x90