문제 정보
문제 정리
곰곰이는 [0][0] 위치에 있고, 상하좌우 4방향으로 이동할 수 있다. 또한, 곰곰이는 [Y][X] 위치에 놓인 치킨을 먹으러 이동하려고 한다.
곰곰이가 치킨을 먹을 수 없도록 장애물을 설치해 접근할 수 없도록 할 때, 설치해야 하는 장애물의 최소 개수를 구해야 한다.
풀이
-
문제를 살펴보자.
치킨은 우하단 모서리에 존재하므로, [Y-1][X], [Y][X-1] 위치에 장애물을 설치하게 될 경우 치킨을 먹을 수 없게 된다.
따라서, 설치해야 하는 장애물의 최대 개수는 2개가 된다. -
즉, 설치해야 하는 장애물의 개수가 0개인지 1개인지 2개인지만 판단하면 된다.
-
우선 격자의 모서리에 벽을 추가로 만들어주자.
그 뒤, 왼쪽, 아래쪽 모서리과 이어진 벽을 2로 마킹하고, 위쪽, 오른쪽 모서리와 이어진 벽을 3으로 마킹한다.
8방향 BFS를 통해 좌하단 모서리에서 시작해 이어진 벽들을 전부 2로 마킹하고, 우상단 모서리에서 시작해 이어진 벽들을 전부 3으로 마킹한다.
- 1번 예제에서 BFS를 끝낸 상태의 격자.
(8방향 BFS이기 때문에 좌상단 모서리와 우하단 모서리에서 이어지는 상황을 막기 위해 두 칸씩 0으로 비워두었다.)
(시작점과 끝점은 빈 공간, 벽과 구별하기 위해 9로 마킹했다.)
- 1번 예제에서 BFS를 끝낸 상태의 격자.
-
두 번의 BFS가 끝났을 때, 좌하단, 우상단 모서리의 마킹 숫자가 같다면 좌상단과 우하단이 이어져 있음을 의미하므로, 곰곰이가 치킨에 접근할 수 없게 된다.
이 경우 추가로 설치해야 할 장애물은 0개가 된다. -
좌하단, 우상단 모서리의 마킹 숫자가 다를 경우, 장애물을 추가로 설치해 곰곰이를 막아야 한다.
격자에 존재하는 모든 0칸에 대해 주변 8방향에 2와 3이 전부 있는 경우, 해당 칸만 장애물을 설치하면 2와 3이 이어지게 된다.
이 경우, 곰곰이가 치킨에게 접근할 수 없게 되므로 추가로 설치해야 할 장애물은 1개가 된다. -
이제 남은 경우는 장애물을 2개 설치해야 하는 경우 뿐이므로 2를 바로 리턴해주면 된다.
-
위 과정을 O(NM)의 시간에 해결할 수 있다.
후기
곰곰컵은 괜찮은 문제가 많은 것 같다.
코드
# 백준 26076
import io
from collections import deque
input = io.BufferedReader(io.FileIO(0), 1<<18).readline
dy = [-1, -1, -1, 0, 0, 1, 1, 1]
dx = [-1, 0, 1, -1, 1, -1, 0, 1]
def BFS(Y, X, grid, start, wallType):
q = deque()
q.append(start)
grid[start[0]][start[1]] = wallType
while q:
curY, curX = q.popleft()
for i in range(8):
nextY = curY + dy[i]
nextX = curX + dx[i]
if 0 <= nextX < X and 0 <= nextY < Y and grid[nextY][nextX] == 1:
q.append((nextY, nextX))
grid[nextY][nextX] = wallType
def solve(Y, X, grid):
grid[1][1] = 9
grid[Y-2][X-2] = 9
# 왼쪽, 아래쪽 벽과 이어진 장애물을 2로, 위쪽, 오른쪽 벽과 이어진 장애물을 3으로 체크
leftType = 2
rightType = 3
BFS(Y, X, grid, [0, X-1], leftType)
if grid[Y-1][0] == 1:
BFS(Y, X, grid, [Y-1, 0], rightType)
# 장애물을 설치하지 않아도 이어진 경우
if grid[0][X-1] == grid[Y-1][0]:
return 0
# 장애물을 1칸만 설치해도 이어지는 경우 체크
for y in range(1, Y-1):
for x in range(1, X-1):
# 0인 칸 8방향에 2와 3이 동시에 있는지 체크
if grid[y][x] == 0:
isTwo = 0
isThree = 0
for i in range(8):
nextT = grid[y+dy[i]][x+dx[i]]
if nextT == 2:
isTwo = 1
elif nextT == 3:
isThree = 1
if isTwo + isThree == 2:
return 1
# 그 외의 경우 전부 2
return 2
def main():
Y, X = map(int, input().split())
grid = [[0, 0] + [1] * X]
for _ in range(Y):
grid.append([1] + list(map(int, input().split())) + [1])
grid.append([1] * X + [0, 0])
print(solve(Y+2, X+2, grid))
main()
