[Python] 2636 - 치즈 (골드4)

1. 문제 설명

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

2636번: 치즈

 

---

2. 아이디어

너비 우선 탐색(BFS, Breadth-First Search)를 처음으로 사용해본 문제였다.

해당 알고리즘을 알면 매우 쉽게 해결할 수 있는 문제이지만,

BFS를 모르면 이해가 안 갈 수 있다.

알고리즘에 대한 설명은 Algorithm 탭에서 한 번에 다루도록 하고

bfs를 사용하여 어떻게 문제를 해결할 수 있는가에 대한 아이디어만 다루도록 하겠다.

 

우선 가장 테두리는 언제나 공기 영역이므로 (0, 0)을 queue에 넣어 이동시킨다.

이때 visited의 역할이 굉장히 중요한데, 방문 처리하는 경우는 두 가지이다.

• 현재 위치가 방문처리 되어 있지 않다면 1로 바꿈
• 현재 위치에서 다음 위치로 이동했는데 치즈 영역이면 1로 바꿈
• 현재 위치에서 다음 위치가 공기 영역이면 1로 바꾸면 안 됨

다른 건 전형적인 bfs 문제인데, 마지막 방문 처리 조건을 나누는 것이 살짝 까다롭다.

 

1. 공기 -> 공기

    : 그냥 다음 공기를 큐에 넣어주면 알아서 반복문을 돌면서 알아서 방문처리하고 할 거 다 한다.

2. 공기 -> 치즈

     : 치즈 위치를 큐에 넣지 않는다는 건 생각해보면 너무 당연한 이야기이다.

       애초에 치즈를 큐에 넣고 이동한다는 건 이 알고리즘 목적과 부합하지 않는다.

       따라서 방문처리를 함으로써 재접근이 불가능하도록 막고 cnt를 1 증가시키고 넘어간다.

 

이번 회차에 녹인 치즈의 개수 cnt는 두 가지 용도로 쓸 수 있는데,

우선 최종적으로 출력해야할 결과값 때문에 필요하고

bfs 반복문 탈출조건으로도 사용할 수 있다.

cnt가 0은 곧 더이상 녹일 치즈가 존재하지 않았다는 의미이므로 누적된 결과를 return하고 출력하면 끝난다.

 

---

3. 코드

move = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def bfs(table, row, col):
    queue = [(0, 0)]
    time = 0

    while queue:
        visited = [[0]*col for _ in range(row)]
        cnt = 0
        for y, x in queue:
            if not visited[y][x]:
                visited[y][x] = 1
                for q, p in move:
                    m_y = y + q
                    m_x = x + p
                    if 0 <= m_y < row and 0 <= m_x < col:
                        if table[m_y][m_x] == 0:
                            queue.append((m_y, m_x))
                        else:
                            table[m_y][m_x] = 0
                            visited[m_y][m_x] = 1
                            cnt += 1
        if cnt == 0:
            return time, result
        else:
            result = cnt
            time += 1
            queue.clear()
            queue = [(0, 0)]

def solution():
    row, col = map(int, input().split())
    table = [list(map(int, input().split())) for _ in range(row)]
    
    time, cnt = bfs(table, row, col)
    print(time)
    print(cnt)

solution()