🦊 게임 맵 최단거리
1. 문제 링크
2. 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def solution(maps):
N = len(maps)
M = len(maps[0])
delta = [
(0, 1), (0, -1), (1, 0), (-1, 0)
]
visit = []
for i in range(N):
visit.append([0] * M)
q = []
q.append((0, 0))
while q:
x, y = q.pop(0)
for dx, dy in delta:
nx = x + dx
ny = y + dy
if 0 <= nx < M and 0 <= ny < N and maps[ny][nx] == 1 and not visit[ny][nx]:
visit[y][x] = 1
q.append((nx, ny))
maps[ny][nx] = maps[y][x] + 1
if maps[N - 1][M - 1] == 1:
return -1
return maps[N - 1][M - 1]
정확성 테스트
채점을 시작합니다. 정확성 테스트 테스트 1 〉 통과 (0.03ms, 10.2MB) 테스트 2 〉 통과 (0.02ms, 10.3MB) 테스트 3 〉 통과 (0.04ms, 10.3MB) 테스트 4 〉 통과 (0.03ms, 10.2MB) 테스트 5 〉 통과 (0.03ms, 10.2MB) 테스트 6 〉 통과 (0.04ms, 10.2MB) 테스트 7 〉 통과 (0.06ms, 10.3MB) 테스트 8 〉 통과 (0.04ms, 10.2MB) 테스트 9 〉 통과 (0.05ms, 10.4MB) 테스트 10 〉 통과 (0.05ms, 10.2MB) 테스트 11 〉 통과 (0.03ms, 10.2MB) 테스트 12 〉 통과 (0.02ms, 10.2MB) 테스트 13 〉 통과 (0.04ms, 10.4MB) 테스트 14 〉 통과 (0.03ms, 10.4MB) 테스트 15 〉 통과 (0.03ms, 10.2MB) 테스트 16 〉 통과 (0.02ms, 10.2MB) 테스트 17 〉 통과 (0.05ms, 10.4MB) 테스트 18 〉 통과 (0.02ms, 10.3MB) 테스트 19 〉 통과 (0.01ms, 10.2MB) 테스트 20 〉 통과 (0.01ms, 10.4MB) 테스트 21 〉 통과 (0.01ms, 10.2MB) 효율성 테스트 테스트 1 〉 통과 (9.43ms, 10.3MB) 테스트 2 〉 통과 (2.92ms, 10.5MB) 테스트 3 〉 통과 (6.36ms, 10.3MB) 테스트 4 〉 통과 (4.31ms, 10.3MB) 채점 결과 정확성: 69.9 효율성: 30.1 합계: 100.0 / 100.0
3. 해설
전형적인 BFS 길찾기 문제
효율성 검사에서 자꾸 시간 초과가 나서 map 자체에 count 를 저장하는 방향으로 바꿈
count 를 하나하나 세는 방법으로는 해결할 수 없는듯