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

2024.09.21 풀이

#0921
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**8)

n=int(input())
arr, res= [], []
maxi=0
dx,dy=[1, -1, 0, 0],[0,0,-1,+1]
for _ in range(n):
    k=list(map(int, input().split()))
    maxi=max(maxi, max(k))
    arr.append(k)

def dfs(a,b,i):
    arr2[a][b]=0
    for j in range(4):
        nx=dx[j]+a
        ny=dy[j]+b
        if 0<=nx<n and 0<=ny<n and arr2[nx][ny]>i:
            arr2[a][b]=0
            dfs(nx, ny, i)

for i in range(0, maxi):
    arr2 = list(map(list, arr))
    cnt=0
    for a in range(n):
        for b in range(n):
            if arr2[a][b]>i:
                cnt+=1
                dfs(a,b,i)
    res.append(cnt)

print(max(res))

---

다른 풀이

#BFS풀이
import sys
from collections import deque
N = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
max_rain = max(map(max, graph))
# 물의 양 조절하기
# 물에 잠기는 영역 확인하기
# 안전한영역의 개수 체크하기
dx = [0,0,-1,1]
dy = [1,-1,0,0]
def bfs(i,j):
    global count
    q = deque()
    q.append((i,j))
    sink[i][j] = True
    count += 1 # 안전한 영역 개수 1 추가
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i] # 상하좌우 확인
            ny = y + dy[i]
            if nx<0 or ny < 0 or nx >= N or ny >= N: # 영역 밖으로 나가면 x
                continue
            if sink[nx][ny]==False: # 상하좌우중 잠겨있지 않은 부분이 있다면
                sink[nx][ny] = True # 잠겼다고 가정시킴
                q.append((nx,ny))
count_list = []
for rain in range(max_rain): # 물의 양 조절
    count = 0 # 안전한 영역의 개수 카운트
    sink = [[False for _ in range(N)] for i in range(N)] # 물에 잠긴 부분 초기화
    for i in range(N):
        for j in range(N):
            if graph[i][j]<=rain:
                sink[i][j]=True # 물에 잠기는 영역 확인하기
    for i in range(N):
        for j in range(N):
            if sink[i][j]==False: # 잠기지 않은 영역일 경우에만
                bfs(i,j) # bfs실행하여 영역모두 잠겼다고 가정하면서 안전한 영역 1 추가시키기
    count_list.append(count) # count_list에 추가 

print(max(count_list)) # count_list중에서 최대값을 출력

#DFS풀이
import sys
sys.setrecursionlimit(100000)

n = int(input())
graph = []
max_num = 0
result = 1

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

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

    for j in low:
        if j > max_num:
            max_num = j

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

        if 0<=nx<n and 0<=ny<n and visited[nx][ny] == 0:
            if graph[nx][ny] > num:
                visited[nx][ny] = 1
                dfs(nx,ny,num)

for i in range(max_num):
    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)
    result = max(result, cnt)

print(result)

• ref

---

체크포인트

• 얕은복사 : arr2=arr -> arr2는 arr과 동일한 참조를 가지므로, arr2를 변경하면 arr도 같이 변경됨. (동일한 메모리 위치를 가리키므로 한쪽을 변경하면 다른쪽도 변경됨)
• 깊은복사 : arr2 = list(map(list, arr)) 또는 arr2 = [arr[i][:] for i in range(len(arr))] -> 새로운 리스트를 생성하며 복사하였기에 독립적으로 동작.