[백준] 2468. 안전 영역

문제

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

2468번: 안전 영역

설계

- 완전탐색 + BFS

 

 

처음 문제를 읽은 후 안전한 영역 개수가 잘 이해되지 않아 문제 이해에만 오랜 시간이 소요되었다.

코드가 조금 지저분해보이는데 조금 더 간결하게 쓰는 코드를 써보도록 노력해야겠다.

import copy

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
visit = [[0]*N for _ in range(N)]
backup_visit = copy.deepcopy(visit)

max_cnt = 0
cnt = 0

def bfs(start):
    global cnt
    q = []
    q.append(start)

    while q:
        x, y, level = q.pop(0)

        for i in range(4):
            dx = [-1, 0, 1, 0]
            dy = [0, 1, 0, -1]
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if arr[nx][ny] > level:         # 잠기지 않은 육지 부분 체크
                    if visit[nx][ny] == 0:
                        visit[nx][ny] = 1
                        q.append((nx, ny, level))
    cnt += 1		# 밟은 땅의 육지를 모두 탐색했으면 카운트+1


for level in range(100):    # 강수량 1~100만큼 순차적으로 증가
    for a in range(N):      # 비가 온 만큼 잠긴다.
        for b in range(N):
            if arr[a][b] > level and visit[a][b] == 0:
                start = (a, b, level)
                visit[a][b] = 1
                bfs(start)
    visit = copy.deepcopy(backup_visit)
    max_cnt = max(cnt, max_cnt)
    cnt = 0

print(max_cnt)