문제 링크: 9205 맥주마시면서 걸어가기
관찰
관찰을 잘해야 고려할 요소가 적어지는 문제
맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다.
-> 한번에 1000m를 이동할 수 있음
박스에 들어있는 맥주는 20병을 넘을 수 없다.
-> 이동 할 수 있는 거리는 최대 1000m
편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다.
-> 편의점에 들리면 1000를 다음 이동 할 수 있다.
맥주를 몇개 살까, 맥주가 몇개 남았을 까는 고려할 필요가 없다. 편의점에 들리면 무조건 맥주 최대 개수만큼 채우는 것이 이득이기 때문.
입력
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)
-> BFS 특성 상 visted(방문 배열) 초기화를 조심해주어야 한다
각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).
다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다.
-> 좌표들을 일차원 리스트에 넣으면
[집, 편의점1, 편의점2 ... , 락 페스티벌] 이 된다
즉 이 문제는 BFS 를 1차원에서 돌리면 되는 문제이다. 그리고
visited(방문 배열) 역시 1차원으로 구현하면 된다.
송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)
-> 맨허튼 거리가 1000이 넘는 곳은 당장은 못간다고 판단하면 된다.
상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다.
-> visited(방문 배열) 이 True 인지 False 인지 판단 하면 된다.
이를 바탕으로 구현 하면 끝이다.
구현
from collections import deque
import sys; input = lambda : sys.stdin.readline().rstrip()
def BFS(x):
visited = [False] * len(mapping)
visited[x] = True
q = deque()
q.append(x)
while q:
n = q.popleft()
x, y = mapping[n]
for i in range(len(mapping)):
# 방문 체크
if visited[i]: continue
# 멘하튼 거리 체크
if abs(x - mapping[i][0]) + abs(y - mapping[i][1]) > 1000: continue
visited[i] = True
q.append(i)
# 락페스티벌의 위치는 mapping[-1]이다
return visited[-1]
T = int(input())
for _ in range(T):
N = int(input()) # 편의점 개수 , 최대 1000 씩 이동 가능 맨하튼으로 0 미만이 되면 움직일수 없다
# 집, 편의점, 락 패스티펄 장소를 저장하는 리스트
mapping = []
# 집
home = tuple(map(int, input().split()))
mapping.append(home)
for _ in range(N):
# 편의점
drugstore = tuple(map(int, input().split()))
mapping.append(drugstore)
# 락 패스티벌
rockfestival = tuple(map(int, input().split()))
mapping.append(rockfestival)
# 집의 위치는 mapping[0]이다
start = 0
print('happy' if BFS(start) else 'sad')일기
단순한 관찰이지만 재밌었다.
프젝 기간인지라 ps에 신경을 들썼는 데, 간만에 재밌게 문제를 풀었다.
