9205번: 맥주 마시면서 걸어가기
송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다.
www.acmicpc.net
from collections import deque
def calculate_distance(x1,y1,x2,y2):
return abs(x1-x2) + abs(y1-y2)
def bfs(x,y):
global end_x, end_y
queue = deque([(x,y)])
visited = set()
while queue:
x, y = queue.popleft()
if calculate_distance(x,y,end_x,end_y) <= 1000:
return True
for i in range(n):
store_x, store_y = store_list[i]
if (store_x,store_y) not in visited:
if calculate_distance(x,y,store_x,store_y) <= 1000:
visited.add((store_x,store_y))
queue.append((store_x,store_y))
return False
t = int(input())
result = []
for _ in range(t):
n = int(input())
start_x, start_y = map(int,input().split())
store_list = [tuple(map(int,input().split())) for _ in range(n)]
end_x, end_y = map(int,input().split())
available = bfs(start_x,start_y)
if available:
result.append("happy")
else:
result.append("sad")
for i in result:
print(i)이번 문제는 맥주를 마시면서 1000M 씩 이동 가능한 상황에서 맥주를 리필할 수 있는 편의점이 있을 때 최종 목적지까지 도착할 수 있는지 여부를 구하는 문제이다.
일단 두 지점 간의 거리를 구하는 함수(calculate_distance)를 선언하고, 처음에는 그리디한 방법으로 문제를 풀었는데 자꾸 틀렸다고 나와서 결국 다른 분의 풀이를 참고하였다.
위 풀이는 내가 생각한 아이디어와 얼핏 비슷해보이지만 특정한 기준으로 편의점을 방문한 나의 풀이와 달리 도달할 수 있는 모든 편의점을 BFS로 방문해가는 완전탐색 방식으로 풀이하였다.
배운 점 및 느낀 점
- 보다 정확한 답을 구하기 위해서는 그리디한 방식으로 풀이하기보다 모든 경우의 수를 탐색할 수 있는 DFS/BFS 알고리즘을 사용하자.
- 2차원 배열이 아닌 그래프나 좌표들의 방문 여부를 체크할 때는 집합 자료형(Set)을 활용하여 체크해주자.(시간 복잡도 최소화를 위해 집합 자료형 사용)