문제 설명 및 제한사항
아이디어 및 해결 방법
코드
def manhattan(r, c, targetr, targetc):
return abs(r - targetr) + abs(c - targetc)
def shortest_path(r, c, targetr, targetc):
# 사전순서에서 제일 빠르면서,
# (r, c)에서 (targetr, targetc)에 가장 빨리 도달하는 경로를 리턴합니다.
res = []
if targetr - r >= 0:
res.append('d' * (targetr - r))
if targetc - c <= 0:
res.append('l' * (c - targetc))
if targetc - c > 0:
res.append('r' * (targetc - c))
if targetr - r < 0:
res.append('u' * (r - targetr))
return ''.join(res)
def solution(n, m, x, y, r, c, k):
R, C = n, m
startr, startc = x-1, y-1
targetr, targetc = r-1, c-1
netr, netc = targetr-startr, targetc-startc
netd = abs(netr) + abs(netc)
if k < netd or (k - netd) % 2 != 0:
return 'impossible'
answer = []
r, c = startr, startc
# 최단거리로 가면 거리가 남을때
# 가능한 한 아래로 갑니다.
while r < R-1 and manhattan(r, c, targetr, targetc) < k:
r += 1
answer.append('d'); k -= 1
# 가능한 한 왼쪽으로 갑니다.
while c > 0 and manhattan(r, c, targetr, targetc) < k:
c -= 1
answer.append('l'); k -= 1
# 그래도 거리가 남는다는 것은 왼쪽 하단에 와있다는 겁니다.
# 남은 거리가 남은 이동횟수와 같아질때까지 rl을 반복합니다.
d = manhattan(r, c, targetr, targetc)
while k > d:
answer.append('rl'); k -= 2
# 마지막으로 최단경로를 붙입니다.
answer.append(shortest_path(r, c, targetr, targetc))
return ''.join(answer)
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges