[백준] 1113번 : 수영장 만들기

1113번: 수영장 만들기

1113번: 수영장 만들기

🤔 문제분석

높이를 1~9 까지 순회하면서 해당 높이에서 수영장을 만들 수 있는 후보를 찾고, 그 후보중에서 만들 수 있는 가장 작은 높이의 수영장으로 만든다. 가장 작은 높이의 수영장이기때문에 다음 높이의 리터레이션에서 물이 다시 채워진다.

바깥쪽에 있는 숫자들은 땅으로 흡수되기 때문에 미리 방문처리를 해준뒤, 그룹을 찾아 나아간다. 그룹을 찾는 과정은 너비우선 탐색으로 해결하였고 해당 그룹에서 가장 작은 높이의 수영장을 찾은뒤에 그 수영장 만큼 물을 채워나아갔다.

💻 코드

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())

pool = [list(str(input().strip())) for _ in range(N)]

ans = 0

def find_min(queue, n):
    min_value = 10
    for y, x in queue:
        for dy, dx in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            ny, nx = dy + y, dx + x
            if N > ny >=0 and M > nx >=0 and int(pool[ny][nx]) != n:
                min_value = min(min_value, int(pool[ny][nx]))
    
    return min_value

for n in range(1, 10):
    visited = [[False for _ in range(M)] for _ in range(N)]
    
    # 외각에 있는 애들 다 방문처리 하기
    for i in range(N):
        for j in range(M):
            if i == 0 or j == 0 or i == N-1 or j == M-1:
                if int(pool[i][j]) == n and not visited[i][j]:
                    visited[i][j] = True
                    queue = deque()
                    queue.append((i, j))
                    
                    while queue:
                        y, x = queue.popleft()
                        
                        for dy, dx in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                            ny, nx = dy + y, dx + x
                            if N > ny >=0 and M > nx >= 0 and not visited[ny][nx] and int(pool[ny][nx]) == n:
                                visited[ny][nx] = True
                                queue.append((ny, nx))
    
    for i in range(N):
        for j in range(M):
            if int(pool[i][j]) == n and not visited[i][j]:
                visited[i][j] = True
                queue = deque()
                queue.append((i, j))
                group = []
                group.append((i, j))
                
                while queue:
                    y, x = queue.popleft()
                    
                    for dy, dx in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                        ny, nx = dy + y, dx + x
                        if N > ny >=0 and M > nx >= 0 and not visited[ny][nx] and int(pool[ny][nx]) == n:
                            visited[ny][nx] = True
                            queue.append((ny, nx))
                            group.append((ny, nx))
                
                
                min_value = find_min(group, n)
                # print(group, min_value)
                if min_value > n:
                    for y, x in group:
                        ans += (min_value - n)
                        pool[y][x] = str(min_value)
    
    # for p in pool:
    #     print(p)

print(ans)

🎯 피드백 및 개선사항

해당 문제를 풀면서 많은 시행착오를 겪었으며, 돌고돌아 결국 문제를 해결하였다. 다른 사람의 문제 풀이를 참고하였을때, 높이가 큰 수영장부터 작은 수영장까지 돌면서, 땅과 인접하지 않으면서 높이가 자기자신보다 작은 수영장을 채워 나가는 식으로 문제를 해결하신 분이 있어서 왜 나는 그런 생각을 못했는지 열심히 해야겠습니다… !! 👏👏👏