-
[탐색] 미로 탈출 명령어 ( 파이썬 )코딩 테스트/프로그래머스 2023. 5. 14. 16:58
문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/150365
문제 풀이
- 방문했던 곳을 다시 가는 것이 허용되는 문제이므로 방문을 최소화하면서 최적의 길을 찾아야 함
- 방향 ( down,up, left,right ) 에 대해 알파벳 순서는 d, l, r, u이다.
- 방문을 최소화 하기 위해 최소 힙을 사용함.
- 알파벳 순서는 dlru 이므로 이것을 반대로 뒤집은 u, r, l d 로 탐색을 진행하면서 각 dist에 (-1 * dir) 을 더할 것
- 아래는 continue 조건 들
- 그리고 어떤 좌표에 있을 때, (그 좌표에서부터 도착 지점까지의 거리 + 지금까지 이동한 횟수) >k 일 경우 어떤 방법을 가더라도 그 좌표에서는 도착 지점을 성립 할 수 없으므로 continue 처리
- gr[n+1][m+1] = 0 그래프를 만들어서 탐색 중인 방식(dist - dir ) 이 gr[x][y] 보다 값이 클 경우 continue 처리
- 아래는 해당 코드
소스 코드
import heapq dx = [-1,0,0,1] dy = [0,-1,1,0] dy = [0,1,-1,0] d = ['u', 'r', 'l', 'd'] def solution(n, m, sx, sy, ex, ey, k): answer = [] q = [] gr = [[0]*(m+1) for i in range(n+1)] heapq.heappush(q,(0,0,sx,sy,[])) while(q): dist, cnt, x, y,dir = heapq.heappop(q) if cnt==k and [x,y]==[ex,ey]: answer=dir break if cnt+abs(ex-x)+abs(ey-y)>k: continue for i in range(4): nx = x + dx[i] ny = y + dy[i] cd = d[i] if nx<=0 or ny<=0 or nx>n or ny>m: continue if dist-i-1>gr[nx][ny]: continue gr[nx][ny]=dist-i-1 heapq.heappush(q,(dist-i,cnt+1,nx,ny,dir+[cd])) return "".join(answer) if answer else "impossible" print(solution(3, 4, 2, 3, 3, 1, 5))
오답 노트
- 탐색 중인 횟수 + (현재 좌표~끝 좌표 거리) >k 이면 아웃이라고 지정 => 시간 초과
- visited [n,m,k] 를 만들어서 visited[nx][ny][cnt] 가 방문했다면 아웃이라고 가정 => 1보다는 괜찮은 시간 초과
- heapq를 만들어서 d = [ 'u', 'r', 'l', 'd' ] 를 만든 뒤 0,-1,-2,-3 을 둬서 우선 순위로 방문 시킴. 알파벳 순서는 dlru니까 반대로 해서 마이너스 값 주고 최소힙 쓴것 => 테스트 31에서 시간 초과
- 방문 그래프를 따로 둬서 현재의 탐색 방식의 계산 값(방향들 더한 값) 방문 그래프에 저장된 숫자보다 크다면 continue를 해줬더니 성공
import heapq dx = [1,0,0,-1] dy = [0,-1,1,0] # 하 좌 우 상 d = ['d', 'l', 'r', 'u'] def solution(n, m, sx, sy, ex, ey, k): answer = [] visited = [[[[] for z in range(k+1)] for i in range(m+1) ] for j in range(n+1)] # 이것도 시간 초과 요소 q = [] heapq.heappush(q,(0,0,sx,sy)) while(q): dist, cnt, x, y = heapq.heappop(q) if cnt==k and [x,y]==[ex,ey]: answer=visited[x][y][cnt] break if cnt>=k: continue for i in range(4): nx = x + dx[i] ny = y + dy[i] cd = d[i] if nx<=0 or ny<=0 or nx>n or ny>m: continue if visited[nx][ny][cnt+1]!=[]: continue visited[nx][ny][cnt+1]=visited[x][y][cnt]+[cd] heapq.heappush(q,(dist+i+1,cnt+1,nx,ny)) return "".join(answer) if answer else "impossible" print(solution(3, 4, 2, 3, 3, 1, 5))
'코딩 테스트 > 프로그래머스' 카테고리의 다른 글
[연습 문제] 숫자 타자 대회 ( 파이썬 ) (0) 2023.06.06 [탐색] 퍼즐 조각 채우기 (파이썬) (0) 2023.06.02 [이분 검색] 외벽 점검 (파이썬, 카카오) (1) 2023.05.12 [파이썬] 가장 긴 팰린드롬 (파이썬) (0) 2023.05.08 [최단거리] 부대 복귀 (파이썬) (0) 2023.05.06