[ 프로그래머스 / LV3 / 파이썬 Python ] 미로 탈출 명령어

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

프로그래머스

이번에 네이버 코딩테스트를 응시하고 깨달은 점은 구현문제가 생각보다 자주 출제되고 어렵게 나온다는 것이다. 카카오에서만 이런 종류의 구현 문제들을 출제하는 줄 알았는데 네이버도 수능과 같은 방식으로 문제를 이해하기 어렵고 이해해도 구현하기 까다롭게 출제하고 있다. 그래서 앞으로는 이런 구현문제들을 많이 풀어보고 사고하는 능력을 길러볼 생각이다.

코드

---

def solution(n, m, x, y, r, c, k):
    answer = ''
    
    k -= abs(x-r)+abs(y-c)
    
    # 홀수인 경우 불가능
    if k < 0 or k%2 != 0:
        return "impossible"
    
    way = {'d':0, 'l':0, 'r':0, 'u':0}
    if x > r:
        way['u'] = x-r
    else:
        way['d'] = r-x
    if y > c:
        way['l'] = y-c
    else:
        way['r'] = c-y
        
    answer += 'd' * way['d']
    nd = min(k//2, n-(x+way['d']))
    answer += 'd'*nd
    way['u'] += nd
    k -= 2*nd
    
    answer += 'l' * way['l']
    nl = min(k//2, y-way['l']-1)
    answer += 'l'*nl
    way['r'] += nl
    k -= 2*nl
    
    answer += 'rl'*(k//2)
    answer += 'r'*way['r']
    answer += 'u'*way['u']
    
    return answer

 

풀이

---

이 문제를 처음 본 누구라도 DFS를 고려해볼 것이라고 생각한다. 나도 마찬가지로 DFS에 완전탐색을 고려했고 n과m이 50이기 때문에 당연하게도 시간초과가 발생했다. 근데 누구는 DFS나 BFS로 해결한 사람도 있다고 하는데 어떻게 한거지...?

 

아무튼 좀 더 생각해보면 이 문제는 완전탐색까지 갈 필요없이 그리디(O(1))로 해결이 가능하다.

 

• 출발점에서 도착점까지 이동하기 위해 가야할 필수방향들이 정해져 있다.
  • 예를 들어, (0,0)에서 (1,3)으로 가기 위해서는 아래로 한칸, 오른쪽으로 3칸을 가야한다.
• 이 필수방향들의 개수의 합과 k의 차이는 중복을 통해 해결해야 한다.
  • 만약 'k-필수방향들의 개수'가 홀수라면 중복이 불가능하다. 왜냐하면 왼쪽으로 한 번 중복이동했다면 오른쪽으로 다시 이동해야 하는데 홀수라면 다시 돌아오지 못하기 때문이다.
• 중복이동은 사전순으로 최대한 갈 수 있을만큼 이동해야 한다.
  • 필수이동도 사전순으로 진행하며 중복이동도 동시에 사전순으로 진행한다.
  • 필수이동을 먼저 수행한 후 그 위치에서 이동할 수 있는 최대 중복이동을 수행한다.
• 마지막에는 'ud'보다는 'rl'이 사전순으로 빠르기 때문에 'rl'로 남은 중복을 수행한다.