제2회 곰곰컵 풀이

A - 치킨댄스를 추는 곰곰이를 본 임스 2 풀이
B - 붙임성 좋은 총총이 풀이
C - 곰곰이와 학식 풀이
D - 오락실에 간 총총이 풀이
E - 곰곰이와 시소 풀이
F - 외로운 곰곰이는 친구가 있어요 풀이
G - 곰곰이와 테트리스 풀이
H - 곰곰아 선 넘지마 풀이
I - 곰곰이의 식단 관리 2 풀이
J - 서커스 나이트 풀이

BOJ 26076 - 곰곰이의 식단 관리 2 링크
(2022.12.01 기준 P5)

문제

N * M 크기의 격자판이 있고, (1, 1) 위치에서 (N, M) 위치로 가려고 한다.
0은 지나갈 수 있는 칸이고 1은 장애물이 있는 칸이라면, (N, M) 위치로 가지 못하게 추가로 놓아야 할 장애물의 최소 개수 출력

알고리즘

0-1 BFS. 자세한 설명은 풀이에서 후술

풀이

처음에 바로 떠올릴 수 있는 방법은 min cut. 하지만 N과 M의 최대가 너무 크다.
다른 방법을 생각해보자.

출처 제2회 곰곰컵 공식 해설

결국은 오른쪽 위(빨간색 부분)와 왼쪽 밑(파란색 부분)이 장애물로 연결되어 있어야 (N, M) 위치로 가지 못하게 된다.

위 그림에서 초록색 부분을 시작점으로 하자.
장애물이 있는 칸은 가중치가 0, 없는 칸은 1로 하여금, 0-1 BFS를 하여
보라색 부분의 결과들의 최소값이 정답이 된다.

코드

import sys; input = sys.stdin.readline
from math import inf
from collections import deque

N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]

# 오른쪽 위에서 왼쪽 밑으로 0-1 BFS
queue = deque()
distance = [[inf] * M for _ in range(N)] # 장애물을 놓은 개수가 거리가 된다.
# 시작점은 (0, 1) ~ (0, M - 1), (1, M - 1) ~ (N - 2, M - 1) 이다.
for j in range(1, M):
    if matrix[0][j]:
        queue.appendleft([0, 0, j])
        distance[0][j] = 0
    else:
        queue.append([1, 0, j])
        distance[0][j] = 1
for i in range(1, N - 1):
    if matrix[i][M - 1]:
        queue.appendleft([0, i, M - 1])
        distance[i][M - 1] = 0
    else:
        queue.append([1, i, M - 1])
        distance[i][M - 1] = 1

answer = 2 # 정답은 2가 최대다. (곰곰이의 시작점의 왼쪽과 밑을 막아버리면 되기 때문)
while queue:
    d, i, j = queue.popleft()
    if distance[i][j] < d:
        continue
    # 진행 방향은 8 방향
    for ii, jj in [(i, j + 1), (i + 1, j + 1), (i + 1, j), (i + 1, j - 1), (i, j - 1), (i - 1, j - 1), (i - 1, j), (i - 1, j + 1)]:
        if 0 <= ii < N and 0 <= jj < M:
            w = matrix[ii][jj] # 가중치 ^ 1
            if distance[ii][jj] > distance[i][j] + (w ^ 1):
                distance[ii][jj] = distance[i][j] + (w ^ 1)
                if w:
                    queue.appendleft([distance[ii][jj], ii, jj])
                else:
                    queue.append([distance[ii][jj], ii, jj])

# 도착점은 (1, 0) ~ (N - 1, 0), (N - 1, 1) ~ (N - 1, M - 2) 이다.
for i in range(1, N):
    answer = min(answer, distance[i][0])
for j in range(1, M - 1):
    answer = min(answer, distance[N - 1][j])

print(answer)