99클럽 코테 스터디 14일차 TIL + BFS

문제

Programmers: 미로 탈출 명령어

• 설명: 출발점에서 도착점까지 k번 이동해서 탈출하여라. 단, 중복해서 이동도 허용하며, 이동하는 명령어의 사전순으로 가장 앞서는 것을 출력하라.

풀이

• 먼저 그래프 탐색의 전형적인 문제라고 생각해 그래프 탐색으로 접근했다.
• 사전순으로 명령이 가장 빠른 것을 선택해야하기 때문에 사전순인 d, l, r, u 순으로 BFS로 탐색해야한다고 생각했다.
  • BFS의 특성상 가장 먼저 특정 위치에 도달한다면 그 위치를 사전순으로 먼저 도착하게 된다.
• 그렇다면 반복을 허용하기 위해서 visited를 어떻게 두어야할까?
  • 위에서 언급했듯이 k번째 이동에서 특정 위치에 도달했다면 그 위치에 도달하는 것이 사전순으로 먼저 도착하는 경우이다.
  • 따라서 visited를 3차원으로 생각해서 visited[k][n][m]으로 잡았다.
  • 이는 k번 움직여서 (n, m)에 도달하였는가?이다.
• 여기서 BFS Queue에 지금까지의 명령어를 저장하게 되면 최대 $2,500$개의 문자열이 $n \times m$인 $2,500$개 저장된다.
  • 이는 문제가 되지 않겠지만 k번 움직이기 때문에 나이브하게 계산하면 $2,500$을 더 곱해야하기 때문에 문자열을 저장하지 않았다.
• 대신 역추적을 사용했다.
  • visited[a][b][c]에 a번 움직여서 (b, c)에 사전순으로 도달하기 위한 이전 위치를 저장하기로 했다.
  • 즉 문제의 1번 예제로 들어보자면, visited[k][r][c]에 사전순으로 도달하기 위해서는 이전에 왼쪽으로 이동했어야하고,
  • 이는 (r, c + 1)에서 와야하기 때문에 visited[k][r][c] = (r, c + 1)가 저장되었다.
  • 최종적으로 만약 visited[k][r][c]에 도달할 수 있다면 거꾸로 역추적을 해주었고, 도달할 수 없다면 impossible을 출력해주었다.

오늘의 회고

• 짜잘짜잘한 잔 실수가 너무 많았다. 변수 이름을 잘못쓴다든지, 엣지 케이스를 잘 생각 못한다든지
• 점점 문제 푸는 속도가 느려지고 실수가 많아진다. 조금 더 집중해서 풀어보자!
• 추가적으로 이 문제는 $O(1)$에 풀 수 있다..!
  • 깊게 풀이를 읽어보진 않았지만 어찌되었든 출발 위치와 도착 위치가 정해져있기 때문에 몇번 왼쪽, 오른쪽, 위, 아래로 이동해야하는지 결정될 것이고 최소 이동거리 외에 이동해야하는 k까지의 남은 거리를 대충 사전순으로 끼워맞추는 식인 것 같았다..! (아니라면 죄송합니다!)
  • 만약 미로에 장애물이나 가중치가 있다면 완전탐색을 하여 풀어야겠지만 장애물이 없다면 위의 방법이 가장 효율적인 풀이다!
• 세상에는 잘하는 사람이 많다! 많은 사람의 풀이를 이해하고 배워보자!

Code

# Programmers150365.py
from collections import deque

INSTS = "dlru" # 사전순 명령어
MOVES = [(1, 0), (0, -1), (0, 1), (-1, 0)] # 사전순 이동 순서

# (x, y) -> (r, c)
def solution(n, m, start_r, start_c, target_r, target_c, target_t):
    # (row, col, time)
    q = deque()
    # visited의 default 값을 (-1, -1)로 두었다.
    visited = [[[(-1, -1) for _ in range(m + 1)] for _ in range(n + 1)] for _ in range(target_t + 1)]

    q.append((start_r, start_c, 0))
    visited[0][start_r][start_c] = (0, 0)

    is_possible = False
    while q:
        curr_r, curr_c, curr_t = q.popleft()

        # k (= target_t) 번 이동해서 r(= target_r), c(= target_c)에 도달하였는가?
        if curr_t == target_t and (target_r == curr_r and target_c == curr_c):
            is_possible = True
            break

        # 목표보다 더 많이 움직이면 의미가 없다.
        next_t = curr_t + 1
        if next_t > target_t:
            continue

        for dr, dc in MOVES:
            next_r, next_c = curr_r + dr, curr_c + dc
            if (0 < next_r <= n) and (0 < next_c <= m):
                # 한번도 방문한적 없다면
                if visited[next_t][next_r][next_c] == (-1, -1):
                    visited[next_t][next_r][next_c] = (curr_r, curr_c)
                    q.append((next_r, next_c, next_t))

    if is_possible:
        ans = []
        curr_t = target_t
        curr_r, curr_c = target_r, target_c
        while curr_t: # k가 0이면 시작점이니 0보다 클 때만 조사
            prev_r, prev_c = visited[curr_t][curr_r][curr_c]

            diff_r, diff_c = curr_r - prev_r, curr_c - prev_c
            for inst, move in zip(INSTS, MOVES):
                if (diff_r, diff_c) == move:
                    ans.append(inst)

            curr_r, curr_c = prev_r, prev_c
            curr_t -= 1

        # 역추적이기 때문에 ans에는 거꾸로 순서가 저장된다. 이를 다시 거꾸로 하여 문자열로 바꿔주었다.
        return ''.join(reversed(ans))

    else:
        return "impossible"