[리트코드 3963] 정확히 하나의 경로를 갖는 격자 만들기 — 경로 셀만 열기

원제: Create Grid With Exactly One Path

문제 요약

행이 m, 열이 n인 격자를 만들고, 왼쪽 위 (0, 0)에서 오른쪽 아래 (m - 1, n - 1)까지 오른쪽 또는 아래로만 이동하는 유효 경로가 정확히 하나가 되도록 합니다. 반환값은 '.'와 '#'로 이루어진 문자열 리스트입니다.

조건과 입출력

1 <= m, n <= 25입니다. '.'는 이동 가능한 칸, '#'는 장애물이며, 경로는 (0, 0)에서 시작해 (m - 1, n - 1)에서 끝나야 합니다. 행과 열 인덱스는 0부터 시작합니다.

예제와 문제 자료

예제 1: 입력 m = 2, n = 3, 출력 ["..#","#.."]. 열린 칸을 따라 (0,0) → (0,1) → (1,1) → (1,2)로만 도착할 수 있습니다. 예제 3: 입력 m = 1, n = 4, 출력 ["...."]. 한 행을 오른쪽으로 이동하는 경로만 존재합니다.

풀이 아이디어

격자를 먼저 전부 장애물로 채운 뒤, 시작점에서 도착점까지 오른쪽 또는 아래로 한 칸씩 이동하며 방문한 칸만 '.'로 바꿉니다. 이 코드에서는 random.choice(moves)가 매번 방향을 고르고, 선택한 이동이 격자 밖으로 나가면 반대 방향으로 한 칸 이동합니다. 따라서 이동은 항상 유효하며, 매 단계마다 행 또는 열 인덱스가 하나 증가하므로 결국 도착합니다. 열린 칸은 이 하나의 단조 경로에 있는 칸뿐입니다. 그 경로의 칸들은 시작점에서 도착점 방향으로 순서대로 이어지며, 다른 열린 칸을 건너뛰는 오른쪽·아래 이동은 생기지 않으므로 유효 경로도 하나뿐입니다.

코드의 핵심

코드는 grid를 m행 n열의 '#'로 초기화하고, grid[0][0]을 '.'로 바꿉니다. moves = [(1,0),(0,1)]에서 dx, dy를 뽑아 (x + dx, y + dy)가 범위 안이면 해당 좌표로 이동해 엽니다. 범위를 벗어나면 x+=dy, y+=dx로 다른 방향을 택합니다. 예제 1에서 한 가능한 이동 순서는 아래와 같습니다. 이는 코드 추적의 한 예이며, 무작위 선택에 따라 다른 유효 격자가 반환될 수 있습니다.

나머지 칸은 계속 '#'이므로 반환 격자는 ["..#","#.."]입니다. 마지막에는 각 행을 "".join(x)로 문자열로 바꾸어 리스트로 반환합니다.

제출 코드

import random

class Solution:
    def createGrid(self, m: int, n: int) -> list[str]:
        grid = [["#"] * n for i in range(m)]

        x,y = 0,0
        grid[0][0] = "."

        moves = [(1,0),(0,1)]
        while x < m-1 or y < n-1:
            dx, dy = random.choice(moves)

            if x + dx < m and y + dy < n:
                x += dx
                y += dy
                grid[x][y] = "."
            else:
                x+=dy
                y+=dx
                grid[x][y] = "."

        return ["".join(x) for x in grid]

복잡도

격자의 칸 수를 mn이라 하면 초기화와 문자열 변환에 O(mn) 시간이 듭니다. 이동 횟수는 오른쪽 이동 n - 1번과 아래 이동 m - 1번의 합인 m + n - 2번이므로 경로 생성은 O(m+n)입니다. 격자 저장에 O(mn) 보조 공간을 쓰며, 반환하는 문자열 리스트도 O(mn) 공간을 차지합니다.

복습 포인트

무작위 선택은 반환되는 격자의 모양을 바꾸지만, 이 구현에서는 경로의 길이와 도착 조건을 바꾸지 않습니다. m = 1 또는 n = 1에서도 한 방향 이동만 가능하며, m = n = 1이면 시작점이 곧 도착점입니다.

출처

문제 원문