개발자 톡
연습문제 톡
나무 섭지
파이썬 시간초과문제
- 등록일
- 2024-04-03 23:09:14
- 조회수
- 352
- 작성자
- wowns123456
import sys from collections import deque n, m = map(int, sys.stdin.readline().split()) grid = [list(sys.stdin.readline().strip()) for _ in range(n)] ds = [(1, 0), (-1, 0), (0, 1), (0, -1)] ghost_pos_list = [] for i in range(n): for j in range(m): if grid[i][j] == 'D': dest_pos = [i, j] elif grid[i][j] == 'G': ghost_pos_list.append([i, j]) elif grid[i][j] == 'N': start_pos = [i, j] def calc_namwoo_short(grid, start_pos): visited = [[False] * m for _ in range(n)] queue = deque([[start_pos[0], start_pos[1], 0]]) while queue: x, y, cnt = queue.popleft() visited[x][y] = cnt if [x, y] == dest_pos: break for dx, dy in ds: if 0<= x+dx < n and 0<= y+dy < m and visited[x+dx][y+dy] == False and grid[x+dx][y+dy] != '#': queue.append([x+dx, y+dy, cnt+1]) return visited[dest_pos[0]][dest_pos[1]] namwoo_short = calc_namwoo_short(grid, start_pos) result = 'Yes' if namwoo_short == False: result = 'No' else: for ghost_pos in ghost_pos_list: ghost_short = abs(ghost_pos[0] - dest_pos[0]) + abs(ghost_pos[1] - dest_pos[1]) if ghost_short <= namwoo_short: result = 'No' break print(result)
파이썬 시간초과가 뜨는데, 어느부분이 문제일까요..? 도와주시면 감사하겠습니다
#나무_섭지