[BOJ] 1113. 수영장 만들기

백준 문제 주소:

www.acmicpc.net/problem/1113

1113번: 수영장 만들기

 

문제 : 주어진 수영장들의 영역(부피)를 구하라.

 

풀이 :

1. DFS / BFS 둘 다 가능한데, BFS가 좀 더 편하게 풀리는 것 같습니다.

2. 수영장 땅의 최대 높이는 9이니까 1~8까지 높이대로 영역(부피)를 구하여 결과값에 각각 저장해줍니다.

3. 수영장 한 곳을 찝어서 BFS/DFS를 돌릴 때, 수영장 밖으로 나가면 거기는 수영장이 아니고, 그 안에서만 돌면 수영장이라고 생각하면 됩니다.

4. 즉, 1~8까지 높이대로 BFS/DFS를 돌릴 때, 선택한 높이보다 높이가 낮거나 같다면 이동가능하고 높이가 높다면 이동 불가능한 곳입니다. 이동하며 높은 숫자로 막혀있으면 수영장, 수영장을 벗어난다면 수영장이 아닌 곳입니다.

 

 처음에 어렵게 생각해서 최대 숫자를 보면서 벽을 먼저 구한 다음 안의 넓이를 구할까 라고 생각했지만, 반대로 작은 수부터 차곡차곡 쌓아가는 형식을 생각하니 쉽게 풀렸습니다.

 

코드 :

from collections import deque
import sys

visited = []
res = 0

def solution():
    global res, visited

    def bfs(x, y, n):
        global res, visited
        Q = deque([(x, y)])
        tmp = [(x,y)]
        sig = True
        visited[x][y] = 1
        cnt = 1
        while True:
            x, y = Q.popleft()
            for _ in range(4):
                rx = x + dx[_]
                ry = y + dy[_]
                if rx == -1 or rx == N or ry == -1 or ry == M:
                    sig = False
                    continue
                if board[rx][ry] <= n and visited[rx][ry] == 0:
                    visited[rx][ry] = 1
                    Q.append((rx, ry))
                    cnt += 1
            if not Q:
                if sig:
                    res += cnt
                return


    N, M = map(int, input().split())
    board = [list(map(int, list(sys.stdin.readline().rstrip()))) for _ in range(N)]
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]
    for num in range(1, 9):
        visited = [[0] * M for _ in range(N)]
        for i in range(N):
            for j in range(M):
                if board[i][j] <= num and visited[i][j] == 0:
                    bfs(i, j, num)
    print(res)
solution()

 

추가 :

테스트 케이스 / 반례 모음

txegg.tistory.com/117

[BOJ] 1113. 수영장 만들기 반례 / 테스트 케이스