[프로그래머스Lv.3] 미로탈출 명령어(파이썬)

https://school.programmers.co.kr/learn/courses/30/lessons/150365

프로그래머스

문제접근

 

1. 경로 중 최단거리??완전탐색+백트래킹을 써야겠네

2. 상하좌우 우선순위를 생각한 탐색이니 탐색돌릴때 신경써야겠다

3. 갔던 곳 다시 갈 수 있다고???????bfs로 어떻게 구하지?

아... k만큼 가야하니깐 그 이상가면 안되니

굳이 visited쓰면서 할 필요는 없겠군.

 

(갔던 곳을 다시 갈 수 있다는 규칙때문에

heap을 활용한 방법도 사용해봤으나

백트래킹이 가장 좋다고 생각해서 dfs로 품)

 

시간초과 이유

 

최단경로 찾았으면 끝내야하는데

그 이상으로 계속 돌다보니 시간초과가 남

 

해결방법

 

1.최단경로 찾을 때, ok라는 변수를 True로 만듬.

2.현재 위치가 경로상 갈 수 없는 거리인지 판단하고 중단시키기

 

코드

import sys

sys.setrecursionlimit(100000)

directions = ['d', 'l', 'r', 'u']
dx = [1, 0, 0, -1]
dy = [0, -1, 1, 0]

ok = False
answer = ''


def solution(n, m, x, y, r, c, k):
    global answer

    def dfs(px, py, cnt, way):
        global ok, answer
        # 최단경로 발견했다면 스탑
        if ok:
            return
        # 현재 거리가 목표지점에서 멀어지면 스탑
        if abs(px - r) + abs(py - c) + cnt > k:
            return

            # k보다 더 많이 이동했다면 스탑
        if cnt > k:
            return

        if not ok and cnt == k:
            if px == r and py == c:
                ok = True
                answer = way
            return

        for d in range(4):
            nx = px + dx[d]
            ny = py + dy[d]

            if nx < 1 or nx > n or ny < 1 or ny > m:
                continue

            dfs(nx, ny, cnt + 1, way + directions[d])

    z = k - abs(x - r) + abs(y - c)
    if z < 0 or z % 2 != 0:
        return 'impossible'

    dfs(x, y, 0, '')
    if not ok:
        return "impossible"

    #     dt = [(1,0,'d'),(0,-1,'l'),(0,1,'r'),(-1,0,'u')]
    #     q=[]
    #     road=[]
    #     heappush(q,[0,x,y,''])
    #     while q:
    #         cnt, px,py,way=heappop(q)
    #         print(way)
    #         if cnt>k:
    #             continue

    #         if px==r and py==c:
    #             if cnt==k:
    #                 ok=True
    #                 answer=way
    #                 break

    #             elif (k - cnt) % 2 == 1:
    #                 return 'impossible'

    #         for d in range(4):
    #             dx,dy,direction = dt[d]
    #             nx = x + dx
    #             ny = y + dy

    #             if nx<1 or nx>n or ny<1 or ny>m:
    #                 continue
    #             if abs(nx-r)+abs(ny-c)+cnt+1>k:
    #                 continue

    #             heappush(q,[cnt+1,nx,ny,way + direction])
    #             break

    #     if answer=='':
    #         return "impossible"

    return answer

 

점검

시간초과로 골머리를 많이 앓았다.

구글링결과,

현재 거리가 목표지점보다 가까운지 아닌지를

염두하지 않아서 삥 돌아갔다.

문제가 막힐 때에는 문제 조건 중

내가 구현 안한게 혹시 있나 보자.