python 그리디하게 풀어봤습니다. 유령최소거리보다, 남우 최소거리가 짧다면 YES
#결국 문제를 쉽게푸는 핵심은 중간에 고스트를 만나서 실패하게될 것을 따지기보단, 결과만을 봤을때 어차피 고스트가 더 거리가 짧다면 이길 수 없는 게임 인것을 인지해야함. import sys from collections import deque #그리고 고스트가 있는경우 고스트의 골인지점 최단거리와 남우 골인지점 최단거리를 비교했을때 #고스트가 민우보다 더 짧은거리면, 민우 패배 #고스트 최단거리는 도착지점(x,y)와 고스트 지점(a,b)를 통해 abs(x-a)+abs(y-b)로 구할수있음. #민우최단거리는 bfs를 써야함. def ghost_min_dist(start,end): return abs(start[0]-end[0])+abs(start[1]-end[1]) def bfs(grid,start,end): row,col=len(grid),len(grid[0]) visited=set() queue=deque([(start[0],start[1],0)])# x , y , 거리 d...
- 연습문제 톡
- 날짜
- 2025-01-06 19:48:27
- 작성자
- jcm5900
- 댓글
- 1