2023 KAKAO BLIND RECRUITMENT 미로 탈출 명령어

문제

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

프로그래머스

 

풀이

사전순으로 가장 빠른 경로를 찾기위해

현재 좌표에서

1. 밑으로 간다. d

2. 왼쪽으로 간다. l

3. 오른쪽으로 간다. r

4 위쪽으로 간다. u

해당 우선순위로 다음좌표로 이동해야한다.

당연하게도 dddd....ddd로 k번가서 (r,c)로 간다는 보장이 없다.

따라서 우린 현재좌표에서 다음좌표가 갈 수 있는 좌표인지 판별한 뒤에 다음좌표로 이동한다.

 

현재좌표가 (cx,cy)라 할때 다음으로 가고싶은 좌표를 (nx,ny)라고 하자.

앞으로 우리가 cnt번 이동가능하다고 하자.(남은 거리가 cnt이고 초기에 cnt = k이다.)

조건1

(nx,ny)가 미로 범위를 빠져나가면 안된다.

조건2

(nx,ny)와 (r,c)의 최단거리가 cnt - 1보다 작아야한다.

최단거리를 구하기위해 (r,c)에서 시작해 탐색알고리즘으로 미로의 모든 좌표에 대한 거리를 구한다.

최단거리 = [[-1] * 가로길이 for _ in range(세로길이)]
q = deque([(r,c)])
while q:
    현재좌표 = q.popleft()
    for 다음좌표 in 상하좌우(현재좌표):
    	if 다음좌표가 미로범위 안 and 최단거리[다음좌표] == -1: #아직 방문 안했을때
            최단거리[다음좌표] = 최단거리[현재좌표] + 1
            q.append(다음좌표)

다음좌표로 이동한 상태에 대한 판별이므로 cnt - 1과 비교한다.

 

 

두 조건은 직관적이다.

핵심은 후술할 조건3이다.

(nx,ny)와 (r,c)의 최단거리를 t라고하자.

(nx,ny)에서 (r,c)로 가는 모든 경로의 거리(이동횟수)는 다음을 만족한다: t + 2s (s >= 0인 정수)

증명

만약 어떤 경로가 수평방향으로 u 수직방향으로 v번 추가적인 이동을 했다고 하자.

t + u + v 

원래 목적으로하는 도착좌표로 이동하기 위해선 반대방향으로 u,v번 추가적으로 이동해야한다.

t + 2(u+v) = t + 2s

 

조건3

(cnt - 1 - 최단거리[다음좌표]) % 2 == 0

 

코드

def solution(Y, X, sy, sx, ey, ex, K):
    # 'd', 'l', 'r', 'u'
    sy,sx,ey,ex = sy-1,sx-1,ey-1,ex-1
    INF = 10 ** 10
    distance = [[-1]*X for _ in range(Y)]
    distance[ey][ex] = 0
    q = deque([(ex,ey)])
    def area(x,y):
        return 0 <= x < X and 0 <= y < Y
    while q:
        x,y = q.popleft()
        for nx,ny in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
            if not area(nx,ny):
                continue
            if distance[ny][nx] == -1:
                distance[ny][nx] = distance[y][x] + 1
                q.append((nx,ny))
    ans = []
    def check(x,y):
        if not area(x,y): # 범위안에 있는가
            return False
        f1 = distance[y][x] <= K - 1 # 이동횟수가 충분한가
        f2 = (K - 1 - distance[y][x]) % 2 == 0 # 충분하다면 유효한가
        return f1 and f2
    while True:
        if check(sx,sy+1): #  priority 1
            sy += 1
            ans.append('d') 
            K -= 1
        elif check(sx-1,sy): # p 2
            sx -= 1
            ans.append('l') 
            K -= 1
        elif check(sx+1,sy): # p 3
            sx += 1
            ans.append('r')
            K -= 1
        elif check(sx,sy-1): # p 4
            sy -= 1
            ans.append('u')
            K -= 1
        else: # oops something wrong!
            break
    if K > 0: # 조건1,2,3에 의해 중간에 이동을 못한 경우
        return "impossible"
    return ''.join(ans)