백준 9205 <맥주 마시면서 걸어가기> Python

Coding Test/BaekJoon_Python

JunOnJuly 2023. 10. 28. 22:40

728x90

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