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

1일 1PS 77일차!

📚 문제

---

[골드 1] - 수영장 만들기

💡 풀이 과정

---

• 수영장의 최대 높이는 9 이기 때문에 9번의 dfs 탐색을 진행하면 된다. ```

13331 21112 12221

위와 같이 주어진 수영장은 3가지로 나누어 생각할 수 있다.

11111 11111 11111

02220 20002 02220

03330 00000 00000

- 3층의 수영장을 각 층별로 분리한 것이다.
- 벽이 아닌 곳은 0 으로 표현했을 때 위와 같고 각 층별로 벽에 둘러쌓인 곳의 넓이를 더해주면 된다.

<br>

def DFS(h): visited = [[False for _ in range(M)] for _ in range(N)]

# 가장자리 부분에 h 보다 작거나 같은 경우에 stack 에 추가.
stack = []
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 pool[i][j] <= h:
                stack.append((i, j))

while stack:
    x, y = stack.pop()
    visited[x][y] = True

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

        if nx < 0 or ny < 0 or nx >= N or ny >= M or visited[nx][ny]:
            continue

        if pool[nx][ny] >= h:
            visited[nx][ny] = True
        else:
            stack.append((nx, ny))

c = 0
for li in visited:
    c += sum(li)

return (M * N) - c

- 처음에는 가장자리부분을 모두 확인해서 전체 둘러쌓인 넓이를 구하려 했다.

333333 311113 313313 311113 333333

- 하지만 위처럼 내부의 벽에 대해서 계산할 수도 없다.

<br>

- 따라서 모든 칸을 방문하는 것을 보장해야한다.
- 각 층의 넓이를 더해주기 위해서는 모든 칸에 대해서 bfs 혹은 dfs 를 진행한다.
- (0, 0) 부터 시작해서 visited 로 구역을 관리하며 모든 곳에 갈 수 있도록 한다.
- 벽의 경우는 continue 하고 벽보다 작은 경우에 대해서만 찾아낸다.
- 탐색 중에 밖으로 벗어나는 경우는 지금까지 계산한 물이 모두 밖으로 흘러가버린다는 뜻이므로 flag = False 이다.
- flag = True 인 경우에만 물이 갇힐 수 있고 이때 cnt 값을 반환하면 된다.

# 📌포인트

---

- visited
    - visited 의 선언 위치에 따라 정답이 바뀔 수 있다.
    - 초기값은 미리 visited 를 설정하고
    - 다음 bfs, dfs 를 진행하기 전에 visited 를 확인하도록 하자!


# 💻 코드

---

dx = [0, 1, 0, -1] dy = [1, 0, -1, 0]

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

#dfs def dfs_height(h): visited = [[False for _ in range(M)] for _ in range(N)] water = 0 for i in range(N): for j in range(M): # 만약 h 와 비교했을 때 물이 채워지지 못하는 벽이라면 visited 만 다시 점검하고 넘어간다. if pool[i][j] >= h: visited[i][j] = True continue

        # 아직 방문하지 않았다면 바로 dfs 실행
        if not visited[i][j]:
            stack = []
            visited[i][j] = True
            stack.append((i, j))
            cnt = 1
            flag = True

            while stack:
                x, y = stack.pop()
                visited[x][y] = True

                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]

                    if nx < 0 or ny < 0 or nx >= N or ny >= M:
                        flag = False
                        continue
                    if visited[nx][ny]:
                        continue

                    if pool[nx][ny] < h:
                        visited[nx][ny] = True
                        cnt += 1
                        stack.append((nx, ny))

            # 다 끝나고 flag = Flag 라면 물이 다 빠져나간다.
            if flag:
                water += cnt

return water

result = 0 for i in range(10): result += dfs_height(i)

print(result)

```