백준 2636 : 치즈

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

2636번: 치즈

https://github.com/HPYoo/swcodingtest/commit/dc688ac924d0d29d25c84cea3a47487ff67d4364

sw coding 2636 update(Baekjoon) · HPYoo/swcodingtest@dc688ac

치즈 먹다 체할뻔

 

1. 오잉 조건 하나가 없네?

 2638 치즈 문제를 먼저 풀고나서 바로 2636을 풀어보니 훨씬 쉬웠고, 풀면서 다른 방식으로 접근해서 풀어봐야겠다라는 생각에 치즈의 외부 판단과 치즈 가장자리 판단을 방문처리함수를 통해 적용시켰다. 이 때 방문 처리 함수는 3차원 배열로 0번째 N X M 크기의 배열에는 외부임을 알리는 배열, 1번째 배열은 치즈의 가장자리임을 알리는 배열로 사용하였다.

큐를 돌리면서 반복적으로 시행을 시키니 불필요하게 코드가 길어지는 일 없이 간단하게 해결할 수 있었다.

내일은 2638 : 치즈에 다시 적용해봐야겠다. 생각 충분히 하니 금방 또 잘 풀리네

 

2. 전체 코드

메모리 : 117168 KB 시간 : 168 ms 풀이시간 : 약 20 ~ 30분? 시간 안재고 풀어서 잘 모르겠음.

여기에서 117 MB 정도의 메모리가 사용되었는데 조건하나 추가했다고 50MB 가 추가 되었다는 건 내가 메모리 활용을 잘 못하고 있다는 반증이겠지? 으쌰으쌰 열공합시다

 

from collections import deque
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
cheese = []
for i in range(N):
    for j in range(M):
        if board[i][j] == 1 : cheese.append([i, j])

visited = [[[False for _ in range(M)] for _ in range(N)] for _ in range(2)]

# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 외부 / 치즈
def solve():
    q = deque([[0, 0]])
    visited[0][0][0] = True
    num = len(cheese)
    it = 0
    last_cnt = 0
    while num > 0 :
        temp = []
        cnt = 0
        while q :
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < N and 0 <= ny < M  :
                    if board[nx][ny] == 0 and not visited[0][nx][ny]:
                        visited[0][nx][ny] = True
                        q.append([nx, ny])
                    if board[nx][ny] == 1 and not visited[1][nx][ny] :
                        temp.append([nx, ny])
                        visited[1][nx][ny] = True
        for x, y in temp :
            board[x][y] = 0
            visited[0][x][y] = True
            cnt += 1
            q.append([x, y])
        last_cnt = num
        num -= cnt
        it += 1
    return [it, last_cnt]

result = solve()
for i in range(2):
    print(result[i])