[2023 KAKAO BLIND RECRUITMENT] 미로 탈출 명령어

문제 풀이

• 생긴게 BFS / DFS 문제처럼 미로찾기 인것 같아 몇 번 시도했는데 시간에서 계속 터져나갔습니다.
• 이후 아예 K만큼만 강제로 루트를 찾아서 시도하는 방법을 시도하였습니다.
• 다만 도착이 가능한 경우에만 시도해야 했습니다. 이 조건이 없으니까 틀리더라구요.
• 미로찾기 형식인 줄 알았는데 사실상 빡구현에 가까운 문제가 아니었나... 싶습니다
• 상세 설명은 주석을 참고하는게 더 나을것 같아 따로 적지 않겠습니다.

def solution(n, m, x, y, ra, ca, k):
    # 사전순 방향. 처음부터 사전순으로 간다고 생각하면 가장 먼저 도달하는게 사전순으로도 빠른 것
    dirs = [('d', 1, 0), ('l', 0, -1), ('r', 0, 1), ('u', -1, 0)]
    result = []

    # 맨허튼 거리를 사용해 남은 거리를 파악. k만큼 움직일 칸이 안되면 도착 불가한거라 impossible
    dist = abs(x - ra) + abs(y - ca)
    if dist > k or (k - dist) % 2 != 0:
        return "impossible"

    # 원래 while문으로 풀려고 했으나 단순히 k번만 반복하면 되고, 사전순으로 방향까지 미리 설정해두면 시간초과가 나지 않는다는 점을 꺠달음
    # 이렇게 하면 visited도 사용하지 않고 bfs로 풀 필요도 없음. 개빡구현 문제라고 생각해야 하는 듯. DFS, BFS로 접근하니 다터짐
    r, c = x, y
    for _ in range(k):
        for d, dr, dc in dirs:
            nr, nc = r + dr, c + dc
            # 범위 벗어나면 쳐냄
            if not (1 <= nr <= n and 1 <= nc <= m):
                continue

            # 남은 거리(주어진 k - 현재까지 지나온 거리 - 1) 로 도착 가능하면 그 방향 도전
            # => 여기서 -1은 다음에 한 칸 더 가야하니까
            remain = k - len(result) - 1 
            new_dist = abs(nr - ra) + abs(nc - ca) # 비교를 위한 맨허튼 거리.
            if new_dist <= remain and (remain - new_dist) % 2 == 0:
                result.append(d)
                r, c = nr, nc
                break

    return "".join(result)

BFS / DFS와의 차이

실제로 BFS와 DFS로 시도했을 때 시간이 대략 100ms가 나오고 이외에는 아예 시간초과가 떴습니다. 다른 분들의 풀이를 보니 저 방식으로도 풀 수 있지만 제 방식이 훨씬 효과적인 것 같습니다. 다만 가장 핵심인것은 k - dist, remain - new_dist % 2 입니다. 해당 조건을 찾아내는지 못찾아내는지에 따라 문제 해결 여부가 결정되더라구요.