[BOJ]2468_안전영역

안전영역

풀이

물의 높이 1부터 ~ 가장 높은 높이까지 반복하며, 안전 영역의 최댓값을 구한다.

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

배열 복사

copy.deepcopy(graph) : 2차원 배열 복사하려면 copy.deepcopy() 사용

graph[:] : 깊은 복사는 1차원 배열만 복사된다.

코드

 
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

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 -1<nx<n and -1<ny<n and visited[nx][ny] == 0 and graph[nx][ny]>h:
            visited[nx][ny] = 1
            dfs(nx,ny,h)

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

high = 0
for i in range(len(graph)):
    for j in graph[i]:
        if j > high:
            high = j

num = 1
for i in range(high):
    visited = [[0]*n for _ 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:
                cnt += 1
                visited[j][k] = 1
                dfs(j,k,i)
    num = max(num,cnt)

print(num)

내가 푼 코드

import sys,copy
sys.stdin =open('in.txt','rt')
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
dx = [1,-1,0,0]
dy = [0,0,1,-1]

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

# 입력값 중 가장 큰 값 
curMax = 0
for i in graph:
    curMax = max(curMax,max(i))

def dfs(x,y,height) : 
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and check[nx][ny] > height : 
            check[nx][ny] = 0 
            dfs(nx,ny,height)

num = 0
for height in range(curMax):
    cnt = 0 
    check = copy.deepcopy(graph) #graph[:]
    for i in range(n):
        for j in range(n):
            if check[i][j] > height:
                cnt += 1
                check[i][j] = 0 
                dfs(i,j,height)
    num = max(num,cnt)         
    
print(num)