[CLASS 4]백준 2638번 - 치즈

2638번 : 치즈

 

 

그림을 보자마자 BFS 문제라는것을 유추할 수 있다.

 

처음에 문제를 대충 읽어서 가장자리에는 치즈가 없다는 사실을 모르고 풀어서 코드가 좀더 길고 시간복잡도도 컸는데, 후에 깨닫고 고쳐서 괜찮은 코드가 된 것 같다.

 

내 코드:

# dawitblog.tistory.com/158
from sys import stdin
from collections import deque
input = stdin.readline

R,C = map(int,input().split())
mat = []
for _ in range(R):
    mat.append(list(map(int,input().split())))

time = 0
moves = [(0,1),(0,-1),(1,0),(-1,0)]

def bfs(startPoints):
    q = deque(startPoints)
    while q:
        nowR,nowC = q.popleft()
        visited[nowR][nowC] = True
        for dr,dc in moves:
            newR = nowR + dr
            newC = nowC + dc

            if 0<=newR<R and 0<=newC<C and not mat[newR][newC] and not visited[newR][newC]:
                visited[newR][newC] = True
                q.append((newR,newC))

# 방문 리스트
visited = [[False]*C for _ in range(R)]
bfs([(0,0)])

while True:
    # 없어질 치즈 리스트
    cl = []
    for r in range(R):
        for c in range(C):
            if mat[r][c]:
                count = 0
                # 4가지 방향 중에서 외부와 접촉한 가짓수 확인
                for dr,dc in moves:
                    newR = r + dr
                    newC = c + dc

                    if visited[newR][newC]:
                        count += 1
                
                if count >= 2:
                    cl.append((r,c))

    if cl:
        for cheese in cl:
            r,c = cheese
            mat[r][c] = 0
        time += 1
    else:
        break
    # 없어진 치즈부터 bfs 수행
    bfs(cl)

print(time)

 

초기에 (0,0)에서 BFS 를 한 번 수행해서 외부 공기는 모두 visited = True가 되도록 해준다. 그 뒤에 완전탐색을 통해 치즈마다 외부 공기와 접한 수를 세어서 2회 이상이라면 치즈를 없앨 리스트 cl에 집어넣고, 후에 cl에 있는 치즈를 한번에 없애준 다음(한번에 없앤다는게 중요하다. 순서대로 없애면 문제가 발생할 수 있다) bfs의 시작점으로 없어진 치즈 위치를 준 뒤 다시 cl을 만드는 작업을 반복하면 된다.