둔필승총

https://www.acmicpc.net/problem/2636

[문제 이해와 내가 푼 방법]

처음에 문제를 읽고 나서는 간단한 탐색 문제라고 생각하였다.

일단 치즈인지 아닌지 판단하여, 제일 겉에 있는 치즈들을 모두 없애주고 사이클을 도는 횟수를 저장하고, 남은 치즈도 따로 저장하는 이 과정을 반복하면 된다고 생각하였다.

이렇게 단순한게 생각하고 접근하였는데 고려해야할 사항이 하나 더 있었다.

제일 겉에 있는 것을 어떻게 판단할 것인가의 문제였는데, 처음에는 0이 있는 칸이 상하좌우에 하나라고 있으면 겉에 있는 치즈라고 생각하였는데, 그것만으로는 판단이 불가능 했다.

해당 그림에서 파란색은 모두 겉에 있는 치즈가 맞지만 빨간색까지 포함시킨다는 점이 문제였다. 

그래서 탐색을 할 때 수정이 필요했다. 

나는 BFS를 사용하였는데, 일단 (0,0)을 BFS의 deque로 받았다. 그리고 방문하였는지 확인해야하기 때문에 visited 배열도 따로 만들어주었다. 

그리고, q에는 아직 방문하지 않았고, 그래프에서 0인 점을 q에 append 한다. 

만약 아직 방문하지 않았고, 그래프에서 1인점은 치즈인 점이다. 해당 좌표는 겉에 있는 치즈이기 때문에 0으로 바꿔주고 갯수를 체크해준다. 그치만 이 점은 q에 넣어주지 않는다. 해당 점을 넣어주게 되면 겉에 있는 치즈 이외에 안쪽에 있는 치즈까지 탐색이 되기 때문이다.

즉, 이렇게 되면 겉에 있는 치즈들과 외부의 0인 점들만 다 탐색을 하게 된다. 위에 있는 빨간색 점들과 빨간색 점들과 파란색 점들로 둘러싸인 0인 점들은 탐색을 하지 못하게 된다. (겉에서 치즈를 탐지하면 q에는 더이상 넣지 않기 때문이다.)

이 반복을 q가 없어질 때까지 하면, 이게 한 사이클이다. 나는 해당 사이클이 끝나면 남아있는 치즈들을 배열에 넣어주었다. 이 부분은 출력을 위해서 left_cheese에 넣어서 마지막에 정답을 출력해주었다. 

(물론 cycle이 한번밖에 없을때 조심해줘야 한다.)

[코드]

from collections import deque

row, col = map(int, input().split())  # 세로, 가로
graph = []
for _ in range(row):
    graph.append(list(map(int, input().split())))
cnt = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def total_cheese(graph):
    cnt = 0
    for i in range(row):
        for j in range(col):
            if graph[i][j] == 1:
                cnt += 1
    return cnt

def isCheese(a, b):  # 해당 칸이 제일 겉의 치즈인지 파악
    q = deque()
    q.append([a, b])
    visited = [[False] * col for _ in range(row)]
    cnt = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < row and 0 <= ny < col:
                if not visited[nx][ny]:
                    if graph[nx][ny] == 0:
                        q.append([nx, ny])
                        visited[nx][ny] = True
                    elif graph[nx][ny] == 1:
                        visited[nx][ny] = True
                        graph[nx][ny] = 0
                        cnt += 1  # 겉의 치즈 개수
    return cnt

time = 0
left_cheese = []
left_cheese.append(total_cheese(graph))
while True:
    cheese = total_cheese(graph)
    time += 1
    left_cheese.append(cheese - isCheese(0, 0))
    if left_cheese[-1] == 0:
        break
print(time)
print(left_cheese[-2])