문제 설명
100만 행 × 100만 열로 이루어진 거대한 격자(grid)가 있다고 가정해 보겠습니다. 격자에는 통행이 금지된 칸(blocked cell) 목록이 주어져 있으며, 우리는 시작 칸(source)에서 출발해 목표 칸(target)에 도달해야 합니다. 매 이동 시에는 상·하·좌·우로 인접한 칸 중 차단 목록에 없는 칸으로만 걸어갈 수 있습니다.
목표는 일련의 이동을 통해 목표 칸에 도달하는 것이 가능한지 판별하는 것입니다.
예를 들어 blocked = [[0,1],[1,0]], source = [0,0], target = [0,3]이 주어지면 결과는 False입니다. 시작점 (0,0)의 오른쪽 칸 (0,1)과 아래쪽 칸 (1,0)이 모두 막혀 있어 어디로도 이동할 수 없기 때문입니다.
해결 전략
격자가 최대 100만 × 100만이므로 전체를 탐색하는 것은 비현실적입니다. 대신 DFS(깊이 우선 탐색)와 "방문 칸 수 임계값"을 활용한 기법을 사용합니다.
핵심 아이디어는 다음과 같습니다. 차단 칸의 개수가 제한적이라면(예: 최대 200개), 막힌 칸들이 만들 수 있는 포위 영역의 크기도 제한됩니다. 따라서 한 지점에서 출발해 임계값(예: 20,000칸) 이상을 자유롭게 방문했다면, 그 지점은 사실상 갇혀 있지 않다고 판단할 수 있습니다.
알고리즘 단계
- blocked 목록을 조회 속도가 빠른 집합(set)으로 변환합니다.
- x, y 좌표, target, 방문 집합 seen을 인자로 받는 dfs() 메서드를 정의합니다.
- (x, y)가 격자 범위를 벗어나거나, blocked에 포함되었거나, 이미 seen에 있는 경우 False를 반환합니다.
- 그렇지 않으면 (x, y)를 seen에 추가합니다.
- seen의 크기가 20,000을 초과하거나 (x, y)가 target이면 True를 반환합니다.
- 상·하·좌·우 네 방향에 대해 재귀적으로 dfs를 호출하고, 그 결과들을 OR로 결합해 반환합니다.
- 최종적으로 source→target 탐색과 target→source 탐색, 양방향 모두 성공해야만 True를 반환합니다. 한쪽 방향만 뚫려 있다면 두 지점은 실제로 만날 수 없기 때문입니다.
구현 예시
class Solution(object):
def isEscapePossible(self, blocked, source, target):
blocked = set(map(tuple, blocked))
def dfs(x, y, target, seen):
if not (0 <= x < 10**6 and 0 <= y < 10**6) or (x, y) in blocked or (x, y) in seen:
return False
seen.add((x, y))
if len(seen) > 20000 or [x, y] == target:
return True
return dfs(x + 1, y, target, seen) or \
dfs(x - 1, y, target, seen) or \
dfs(x, y + 1, target, seen) or \
dfs(x, y - 1, target, seen)
return dfs(source[0], source[1], target, set()) and \
dfs(target[0], target[1], source, set())
ob = Solution()
print(ob.isEscapePossible([[0,1],[1,0]], [0,0], [0,3]))입력
[[0,1],[1,0]], [0,0], [0,3]
출력
False
복잡도 분석
DFS는 각 칸을 최대 한 번씩만 방문하므로, 탐색 범위는 임계값인 약 20,000칸으로 제한됩니다. 따라서 격자 크기와 무관하게 시간 복잡도는 O(B + T), 공간 복잡도 역시 O(B + T)입니다. 여기서 B는 차단 칸의 개수, T는 임계값(20,000)입니다.