[백준] Python 2468 안전영역

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

2468번: 안전 영역

문제에 대한 설명은 위와 같다.

 

나는 이번에도 반복문을 사용해서 풀려고 했다. 한 반복마다 계속 배열을 복사해 안전 지역일 경우 왼쪽과 위를 비교해서 안전지역이라면 카운트를 늘리지 않는 방법을 생각했다. 그러나 복제가 되지 않는다는 문제와 오른쪽과 아래를 비교하지 않는다는 문제(위 외쪽이 막혀있고 아래 오른이 열려있는 경우 카운트가 세진다) 때문에 풀지 못했다. 그리고 다른 사람들이 푼 코드를 보고 이해하려 노력했다.

 

n = int(input())
area = []
high = 0
result = 0
for i in range(n):
    row = list(map(int, input().split()))
    area.append(row)
    high = max(high, max(row))
for i in range(high):
    curr = [[0] * n for m in range(n)]
    count = 0
    for k in range(n):
        for j in range(n):
            if (area[j][k] <= i):
                curr[j][k] = 0
            else:
                curr[j][k] = 1
                count += 1
                if ((j-1 >= 0 and curr[j-1][k] == 1) or (k-1 >= 0 and curr[j][k-1] == 1)):
                    count -= 1
    result = max(result, count)

print(result)

위에는 내가 푼거 오답

 

아래는 다른 사람들의 코드다 정답

from collections import deque

n = int(input())
graph = []
maxNum = 0

for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(n):
        if graph[i][j] > maxNum:
            maxNum = graph[i][j]


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


def bfs(a, b, value, visited):
    q = deque()
    q.append((a, b))
    visited[a][b] = 1

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] > value and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    q.append((nx, ny))


result = 0
for i in range(maxNum):
    visited = [[0] * n for i in range(n)]
    cnt = 0

    for j in range(n):
        for k in range(n):
            if graph[j][k] > i and visited[j][k] == 0:
                bfs(j, k, i, visited)
                cnt += 1

    if result < cnt:
        result = cnt

print(result)

bfs를 이용했다. 강수량을 0부터 지역의 최대 높이까지 하나씩 올려서 비교한다. 이때 한 요소가 방문한 적 없고 강수량보다 높다면 bfs를 이용해 그 안전지역과 연결된 모든 곳을 체크하고 해당 강수량의 카운트를 늘린다. 그리고 그 카운트 중 가장 높은 카운트를 결과값으로 출력한다. 

 

아휴 똑똑한 사람 왜이리 많을까