[Python] boj no. 1113 : 수영장 만들기

Problem

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

Idea

수영장의 높이가 1 이상 9 미만이므로 1~8까지 루프문을 돌려 각 높이에 해당되는 요소를 찾을 때마다 해당 면적을 bfs로 계산했다. 탐색 시에 범위가 리스트를 벗어날 경우 물이 고일 수 없는 것으로 간주하여 총 면적에 포함하지 않았다. 탐색 이후 방문한 요소마다 1을 더해 높이 1만큼 물이 차 있는 상황으로 만들어 다음 높이의 면적 계산에도 포함될 수 있도록 했다.

Code

import sys
from collections import deque

def bfs(y, x, lvl):
    mount = 0
    flag = True
    queue = deque()
    map[y][x] = lvl+1   # 해당 레벨 방문 처리
    queue.append((y, x))

    while queue:
        py, px = queue.popleft()
        mount += 1

        for i in range(4):
            ny = py + dy[i]
            nx = px + dx[i]

            if ny < 0 or ny >= N or nx < 0 or nx >= M: 
            # 수영장 외곽과 닿으면 flag=False로 하여 총량에 추가하지 않음.
                flag = False
            elif map[ny][nx] == lvl:
                queue.append((ny, nx))
                map[ny][nx] = lvl+1

    if flag == True:
        return mount
    else:
        return 0

input = sys.stdin.readline

N, M = map(int, input().split())
map = [list(map(int, input().rstrip())) for _ in range(N)]

sum = 0
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
for w in range(1, 9):
    for i in range(N):
        for j in range(M):
            if map[i][j] == w:
                sum += bfs(i, j, w)

print(sum)

Comment