태야

<내 코드>

import copy

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

answer = 0

def bfs():
    global answer
    v = copy.deepcopy(virus)  # 원본 유지한채 복사(바이러스 좌표값)
    tmp = [[0]*M for _ in range(N)]
    # 지도 복사
    for i in range(N):
        for j in range(M):
            tmp[i][j] = maps[i][j]

    # 4방향 탐색 후 바이러스 감염
    while len(v) != 0:
        vir = v.pop()
        vir_x = vir[0]
        vir_y = vir[1]

        for k in range(4):
            nx = vir_x + dx[k]
            ny = vir_y + dy[k]
            if 0 <= nx < N and 0 <= ny < M:
                if tmp[nx][ny] == 0:
                    tmp[nx][ny] = 2
                    v.append([nx, ny])
    # 0(안전구역) 갯수 파악
    result = 0
    for i in tmp:
        for j in i:
            if j == 0:
                result += 1

    answer = max(result, answer)

# 벽 3개를 세우는 모든 경우의 수
def wall(cnt):
    if cnt == 3:
        bfs()
        return

    for i in range(N):
        for j in range(M):
            if maps[i][j] == 0:
                maps[i][j] = 1
                wall(cnt+1)
                maps[i][j] = 0
                
N, M = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(N)]

virus = []

# 바이러스 좌표값 저장
for i in range(N):
    for j in range(M):
        if maps[i][j] == 2:
            virus.append([i, j])
wall(0)
print(answer)

벽 3개를 세우는 방법을 알지 못해 다른 사람들의 코드를 참고했다. 여기서 입력의 크기가 크지 않기 때문에 브루트포스를 사용해 벽3개를 세우는 경우의 수를 다 구했다. 모든 경우의 수를 구하는 코드를 이해하는데 쉽지 않았다..

앞으로 자주 사용될 것 같다.

<내 코드>

import sys
sys.setrecursionlimit(10000)

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


def dfs(x, y, h):

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

        if(0 <= nx < N) and (0 <= ny < N):
            if arr[nx][ny] > h and done[nx][ny] == 0:
                done[nx][ny] = 1
                dfs(nx, ny, h)


N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
ans = 0

for k in range(max(map(max, arr))):  # 주어진 배열에서 가장 큰값만큼 반복
    # 매번 초기화
    cnt = 0
    done = [[0]*N for _ in range(N)]

    # 입력 받은 arr배열 탐색
    for i in range(N):
        for j in range(N):
            if arr[i][j] > k and done[i][j] == 0:
                done[i][j] = 1
                cnt += 1
                dfs(i, j, k)

    ans = max(ans, cnt)


print(ans)

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

이 문제에서 중요한 것이 물의 높이 1부터 ~ 가장 높은 높이까지 반복하며, 안전 영역의 최댓값을 구하는 거다. 

max(map(max, arr)) 구문을 통해서 입력 배열에서 가장 큰 값(이 예에서는 9)을 구할 수 있다. 그리고 매 dfs 탐색이 끝나면 이전 안전 영역 개수(ans)와 현재 탐색의 안전 영역 개수(cnt) 중 큰 값을 비교해 담는다.