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

(x, y)에서 (r, c)까지 가는데 k만큼 걸리도록 가게 했을 때 명령중 사전순으로 가장 빠른 명령을 구하는 문제이다.

Python

1차 실패 - BFS

def solution(n, m, x, y, r, c, k):
    answer = ''
    
    dy = [0, 0, 1, -1]
    dx = [1, -1, 0, 0]
    direc = ["d", "u", "r", "l"]
    
    que = [(y, x, 0, "s")]
    
    idx = 0
    
    out = []
    
    while idx < len(que):
        nowy, nowx, cost, di = que[idx]
        idx += 1
        
        if nowy == c and nowx == r and cost == k:
            out.append(di)
            continue
        
        for d in range(4):
            ny = nowy + dy[d]
            nx = nowx + dx[d]
            
            if 1 <= ny <= m and 1 <= nx <= n and cost < k:
                que.append((ny, nx, cost + 1, di + direc[d]))
    
    out.sort()
    
    
    return out[0][1:] if out  else 'impossible'

BFS로 탐색하면서 거리가 k이고 r, c에 도착했을 때 명령만 out에 담아서 사전순으로 정렬했을 때 가장 빨리 나오는 것을 출력하도록 했다.

처음엔 visited 없이 탐색하기에 무한루프에 빠지는 것이 아닌가 싶었지만 k라는 제한이 있어서 괜찮을 것이라 생각했다. 그러나 k가 최대 2500이었기에 시간초과가 발생했다.

2차 실패 - BFS

def solution(n, m, x, y, r, c, k):
    answer = ''
    
    dy = [0, 0, 1, -1]
    dx = [1, -1, 0, 0]
    direc = ["d", "u", "r", "l"]
    
    visited = [[True] * m for _ in range(n)]
    
    que = [(x, y, 0, "s")]
    visited[x-1][y-1] = False
    
    idx = 0
    
    out = []
    
    while idx < len(que):
        nowx, nowy, cost, di = que[idx]
        idx += 1
        
        if nowx == r and nowy == c and k%2 == cost%2:
            out.append((di[1:]))
            
        for d in range(4):
            ny = nowy + dy[d]
            nx = nowx + dx[d]
            
            if 1 <= ny <= m and 1 <= nx <= n and visited[nx-1][ny-1]:
                que.append((nx, ny, cost + 1, di + direc[d]))
                visited[nx-1][ny-1] = False
    # du, ud, lr, rl => du, lr, rl, ud
    if out:
        out.sort()
        ans = out[0]
        direction = [0, 0] # 'du', 'lr'

        dif = (k - len(ans)) // 2
        idx = 0
        
        ny = y
        nx = x
    
        while idx < len(ans) and ans[idx] == 'd':
            nx += 1
            answer += "d"
            idx += 1

        while nx < n and dif > 0:
            dif -= 1
            answer += "d"
            nx += 1
            direction[0] += 1

        while idx < len(ans) and ans[idx] == 'l':
            ny -= ny
            answer += "l"
            idx += 1

        while ny > 1 and dif > 0:
            dif -= 1
            answer += 'l'
            direction[1] += 1
            ny -= 1
        
        while dif>0:
            dif-=1
            answer += 'rl'
            
        
        while idx < len(ans) and ans[idx] == 'r':
            ny += 1
            answer += "r"
            idx += 1
        
        for d in range(direction[1]):
            ny += 1
            answer += 'r'
            
        
        while idx < len(ans) and ans[idx] == 'u':
            nx -= 1
            answer += 'u'
            idx += 1
        
        for d in range(direction[0]):
            nx -= 1
            answer += 'u'

        return answer
    else:
        return 'impossible'

visited를 넣어서 rc까지 가는 가장 짧은 경로를 BFS로 구한 후 남은 k를 2로 나눈 수 만큼 d나 l을 넣고 반대편에 u와 r을 넣는 방식을 선택했다.

그래서 최단 경로에서 d를 먼저 꺼내고 그 다음 k/2동안 미로를 벗어나지 않는 선에서 d를 추가로 더해주었다.
그 다음 l을 꺼내고 남은 k/2동안 미로를 벗어나지 않는 선에서 l을 추가로 더했다.
그러고 나서도 k/2가 남는다면 그만큼은 rl을 추가해주고, 나머지 경로와 k/2만큼 추가한 r과 u를 더해주었다.
하지만 실패했다.

3차 시도 - 경로 계산

질문하기를 참고해서 해결했다.
https://school.programmers.co.kr/questions/42052

def solution(n, m, x, y, r, c, k):
    answer = ''
    dist = abs(x-r)+abs(y-c)
    k -= dist
    if k < 0 or k%2 != 0:
        return "impossible"
    
    direction = {'d':0, 'l':0, 'r':0, 'u':0}
    if x > r:
        direction['u'] += x-r
    else:
        direction['d'] += r-x
    if y > c:
        direction['l'] += y-c
    else:
        direction['r'] += c-y
        
    answer += 'd'*direction['d']
    d = min(int(k/2), n-(x+direction['d']))
    answer += 'd'*d
    direction['u'] += d
    k -= 2*d
    
    answer += 'l'*direction['l']
    l = min(int(k/2), y-direction['l']-1)
    answer += 'l'*l
    direction['r'] += l
    k -= 2*l
    
    answer += 'rl'*int(k/2)
    answer += 'r'*direction['r']
    answer += 'u'*direction['u']
    return answer

일단 이게 어느방향으로 갈 수 있고 장애물도 없고 하기에 BFS로 최단경로 구하는 것은 의미가 없었다. 그냥 좌표 빼서 최단 거리를 구하면 됐다.

그리고 실패하는 경우는 k에서 최단 거리를 뺐을 때 k가 모자라거나, 결과가 짝수가 아닐 때 무조건 실패한다. 짝수가 아니라면 rl이나 du 처럼 다시 원래자리로 돌아올 수 없기 때문이다.

위 코드에서는 먼저 최단 경로를 빼고, direction이라는 딕셔너리를 만들어서 방향별로 최단 경로가 어떻게 되는지 구했다.

r까지 도달할 때 필요한 d를 answer에 추가해주고, k/2만큼 d로 이동하는데 n을 만난다면 n까지의 거리만큼 d를 추가해주었다. u에는 추가한 d만큼 돌아와야하기에 u에도 숫자를 더했다.

l에 대해서도 c까지 도달할 만큼 answer에 추가해주고, 남은 k/2만큼 l로 이동하는데 중간에 m을 만나면 그 거리만큼 l을 추가해준다. r에는 추가한 l만큼 숫자를 올려주었다.

그래도 k/2가 남는다면 남은 k/2만큼 rl을 추가해준다. rrrr이나 uuu보다 rl이 가장 사전순으로 빠르기 때문이다.
마지막으로 r과 u를 각각 수만큼 더해줌으로써 답을 구했다.