[백준 알고리즘] 2468.안전영역

 

 

첫번째는 풀이는 단계를 나눠

 

1) 높이의 최댓값, 최솟값을 구하고,

 

2) (최솟값부터 최댓값까지 하나씩 대입하여) 회색 영역을 찾고,

 

3) 잠기지 않는 부분을 count 해 최댓값을 저장

 

이렇게 풀었다.

 

 

그런데 다 풀고 나서 리팩토링하기 위해 다시 보니

 

굳이 회색영역을 찾지 않아도 됨을 알게 되었다.

 

그래서 높이값과 방문표시를 사용하여 회색영역을 찾는 부분을 없앴더니 조금 속도가 빨라졌다.

 

 

 

 

 

 

import sys

N = int(sys.stdin.readline())
areas = []
safe = 0
gray_area = [[0]* N for _ in range(N)]
safe_area = [[0]* N for _ in range(N)]
delta = [(1, 0), (-1, 0), (0, 1), (0, -1)]
stack = []


# 물에 잠기는 지역 찾기
def check_gray_areas():
    global safe
    height = min_h
    while True:
        if height > max_h : break
        for i in range(N):
            for j in range(N):
                if gray_area[i][j] <= height:
                    gray_area[i][j] = 0

        for i in range(N):
            for j in range(N):
                safe_area[i][j] = gray_area[i][j]
        ans = find_safe_area()
        if safe < ans :
            safe = ans
        height += 1

    return safe


# 잠기는 지역 제외한 안전영역 갯수 세기
def find_safe_area():
    cnt = 0
    for i in range(N):
        for j in range(N):
            if safe_area[i][j] != 0:
                cnt += 1
                stack = [(i, j)]
                safe_area[i][j] = 0
                while stack:
                    r, c = stack.pop()
                    for dt in range(4):
                        nr = r + delta[dt][0]
                        nc = c + delta[dt][1]
                        if 0 <= nr < N and 0 <= nc < N and safe_area[nr][nc] != 0:
                            safe_area[nr][nc] = 0
                            stack.append((nr, nc))
    return cnt


for i in range(N):
    areas.append(list(map(int, sys.stdin.readline().split())))


# 최대 최솟값 찾기
min_h = 101
max_h = 0
for i in range(N):
    for j in range(N):
        if areas[i][j] < min_h :
            min_h = areas[i][j]
        if areas[i][j] > max_h:
            max_h = areas[i][j]

for i in range(N):
    for j in range(N):
        gray_area[i][j] = areas[i][j]

if min_h == max_h:
    print(1)
else:
    print(check_gray_areas())



#### 발전 시킨 풀이
#### 회색 영역 계산없이 높이를 이용해 바로 안전영역 갯수 세기


def find_safe_area(min_h, max_h):
    ans = 0
    height = min_h
    while height < max_h:
        visited = [[0] * N for _ in range(N)]
        cnt = 0
        for i in range(N):
            for j in range(N):
                if areas[i][j] > height and visited[i][j] == 0:
                    cnt += 1
                    stack = [(i, j)]
                    visited[i][j] = 1
                    while stack:
                        r, c = stack.pop()
                        for dt in range(4):
                            nr = r + delta[dt][0]
                            nc = c + delta[dt][1]
                            if 0 <= nr < N and 0 <= nc < N and visited[nr][nc] == 0:
                                if areas[nr][nc] > height:
                                    visited[nr][nc] = 1
                                    stack.append((nr, nc))
        if ans < cnt:
            ans = cnt
        height += 1

    return ans


N = int(sys.stdin.readline())
areas = []
delta = [(1, 0), (-1, 0), (0, 1), (0, -1)]
stack = []

for i in range(N):
    areas.append(list(map(int, sys.stdin.readline().split())))


# 최대 최소 구하기
min_h = 101
max_h = 0
for i in range(N):
    for j in range(N):
        if areas[i][j] < min_h :
            min_h = areas[i][j]
        if areas[i][j] > max_h:
            max_h = areas[i][j]


if min_h == max_h:
    print(1)
else:
    print(find_safe_area(min_h, max_h))