0은 빈 셀을, 1은 벽을 나타내는 2차원 이진 행렬이 주어졌다고 가정해 보겠습니다. 이때 왼쪽 상단 셀과 오른쪽 하단 셀 사이에 어떤 경로도 존재하지 않도록 만들기 위해 벽으로 바꿔야 하는 셀의 최소 개수를 구해야 합니다. 단, 왼쪽 상단 셀과 오른쪽 하단 셀에는 벽을 설치할 수 없으며, 이동은 상·하·좌·우 방향으로만 가능하고 대각선 이동은 허용되지 않습니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 |
이 경우 출력값은 2이며, 벽을 배치한 결과는 다음과 같습니다.
| 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 |
문제 해결 접근 방식
이 문제는 그래프 이론의 단절점(Articulation Point) 개념을 활용하면 효율적으로 해결할 수 있습니다. 단절점이란 해당 정점을 제거했을 때 그래프가 둘 이상의 연결 요소로 분리되는 정점을 의미합니다. 전체 알고리즘은 다음과 같은 단계로 진행됩니다.
R := 행렬의 행 개수, C := 행렬의 열 개수로 초기화합니다.
visited := 방문 여부를 저장하는 집합, tin := 각 정점의 진입 시간, low := 서브트리에서 도달 가능한 최소 진입 시간을 저장하는 맵을 생성합니다.
timer := 0, bridge_pts := 단절점을 저장할 집합, par := 부모 정점 정보를 저장하는 맵을 준비합니다.
src := (0, 0), tgt := (R − 1, C − 1)로 시작점과 목표점을 설정합니다.
dfs() 함수를 정의합니다. 이 함수는 정점 v와 부모 parent를 인자로 받습니다.
v를 방문 처리하고, par[v], tin[v], low[v]를 설정한 뒤 timer를 1 증가시킵니다.
v의 모든 이웃 정점 to에 대해 다음을 반복합니다.
to가 부모와 같으면 건너뜁니다.
to를 이미 방문했다면 low[v]를 min(low[v], tin[to])로 갱신합니다.
그렇지 않으면 dfs(to, v)를 재귀 호출한 후 low[v]를 min(low[v], low[to])로 갱신합니다. 이때 low[to] >= tin[v]이고 parent가 null이 아니라면 v를 bridge_pts에 추가합니다.
자식 수(children)를 1 증가시킵니다.
parent가 null이고 자식 수가 2보다 크다면 v를 bridge_pts에 추가합니다(루트 정점의 단절점 판별 조건).
bfs() 함수를 정의합니다. 이 함수는 시작 정점 root를 인자로 받습니다.
Q := root 하나만 담은 덱(deque)을 생성하고, visited 집합에 root를 넣습니다.
Q가 빌 때까지 다음을 반복합니다.
Q에서 마지막 원소 v를 꺼냅니다.
v가 tgt와 같으면 True를 반환합니다.
v의 이웃 중 아직 방문하지 않은 w를 visited에 추가하고 Q의 왼쪽에 삽입합니다.
반복이 끝나면 False를 반환합니다.
메인 흐름은 다음과 같습니다.
dfs(src, null)를 호출합니다.
tgt가 par에 없다면 애초에 경로가 없으므로 0을 반환합니다.
bridge_pts의 모든 좌표 (i, j)에 대해 matrix[i, j] := 1로 변경합니다.
bfs(src)가 True라면 벽 2개가 필요하므로 2를 반환합니다.
그렇지 않다면 벽 1개로 충분하므로 1을 반환합니다.
구현 예시
아래 코드를 통해 더 잘 이해해 보겠습니다.
from collections import deque
class Solution:
def solve(self, matrix):
R = len(matrix)
C = len(matrix[0])
def get_neighbors(i, j):
for ii, jj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ii < R and 0 <= jj < C and matrix[ii][jj] == 0:
yield ii, jj
visited = set()
tin = {}
low = {}
timer = 0
bridge_pts = set()
par = {}
src = (0, 0)
tgt = (R - 1, C - 1)
def dfs(v, parent):
nonlocal timer
visited.add(v)
par[v] = parent
tin[v] = timer
low[v] = timer
timer += 1
children = 0
for to in get_neighbors(*v):
if to == parent:
continue
if to in visited:
low[v] = min(low[v], tin[to])
else:
dfs(to, v)
low[v] = min(low[v], low[to])
if low[to] >= tin[v] and parent is not None:
bridge_pts.add(v)
children += 1
if parent is None and children > 1:
bridge_pts.add(v)
def bfs(root):
Q = deque([root])
visited = set([root])
while Q:
v = Q.pop()
if v == tgt:
return True
for w in get_neighbors(*v):
if w not in visited:
visited.add(w)
Q.appendleft(w)
return False
dfs(src, None)
if tgt not in par:
return 0
for i, j in bridge_pts:
matrix[i][j] = 1
if bfs(src):
return 2
return 1
ob = Solution()
matrix = [
[0, 0, 0, 0],
[0, 1, 0, 0],
[0, 1, 1, 0],
[0, 0, 0, 0],
]
print(ob.solve(matrix))입력
[
[0, 0, 0, 0],
[0, 1, 0, 0],
[0, 1, 1, 0],
[0, 0, 0, 0],
]출력
2
정리
이 알고리즘은 DFS 기반의 Tarjan 단절점 탐색 기법을 사용해 경로 차단에 핵심이 되는 셀을 먼저 찾아낸 뒤, 해당 셀들을 벽으로 바꾸고 BFS로 연결성을 재검증하는 방식으로 동작합니다. 덕분에 모든 조합을 무작위로 시도하는 브루트포스 방식보다 훨씬 효율적으로 최소 벽 개수를 구할 수 있습니다.