파이썬 알고리즘 303번 | [백준 2468번] 안전구역 - 그래프

127. 큰 수 A+B

1) 어떤 전략(알고리즘)으로 해결?

그래프 이론
브루트포스 알고리즘
그래프 탐색
너비 우선 탐색
깊이 우선 탐색

2) 코딩 설명

• 주석

<내 풀이>

# https://www.acmicpc.net/problem/2468 안전 영역
from collections import deque
import sys

# 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사
N = int(sys.stdin.readline().rstrip())
area = []
max_height = -1
answer = 0

for i in range(N) : 
    now_list = list(map(int, sys.stdin.readline().split()))
    area.append(now_list)
    max_height = max(max_height, max(now_list))

dirr = [-1,1,0,0]
dirc = [0,0,-1,1]

def bfs(row, col ) :
    q = deque()
    q.append((row,col))
    while q : 
        nowr, nowc = q.popleft()
        for i in range(4) : 
            tmpr, tmpc = nowr+dirr[i], nowc+dirc[i]
            if 0<=tmpr<N and 0<=tmpc<N and area[tmpr][tmpc]!=-1 and visited[tmpr][tmpc]==0 : 
                visited[tmpr][tmpc] = 1
                q.append((tmpr, tmpc))

def count_safe_area(area ) : 
    cnt = 0
    for i in range(N) :
        for j in range(N) :
            # 방문안했으며 잠기지 않는 아이를 발견했으면 
            if visited[i][j]==0 and area[i][j]!=-1 : 
                visited[i][j] = 1 # 방문 처리 해주고
                cnt+=1 # 현재 아이의 영역을 dfs 로 구할 때마다 영역 하나씩 찾는 것임 
                bfs(i,j)
    return cnt

# 장마철에 내리는 비의 양에 따라서 
for rain in range(0, max_height+1) : # 비 높이가 1부터 시작한다고 생각했는데, 비가 오지 않는 0부터도 생각해줬어야 했다! 
    # 비에 잠긴 곳은 -1 처리 
    visited = [ [0 for _ in range(N+1)] for _ in range(N+1) ]
    for r in range(N) :
        for c in range(N) : 
            if area[r][c]!=-1 and area[r][c]<=rain : 
                # 잠기지 않았고, 높이가 rain 높이보다 낮으면 잠김 처리
                area[r][c] = -1 # 잠김 표시는 -1로 처리해준다.
                
    answer = max(answer, count_safe_area(area))

print(answer)

< 내 틀렸던 풀이, 문제점>

(1) DFS 풀이 - 메모리 초과

# https://www.acmicpc.net/problem/2468 안전 영역
import sys
sys.setrecursionlimit(10**5)
# 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사
N = int(sys.stdin.readline().rstrip())
area = []
max_height = -1
answer = 0

for i in range(N) : 
    now_list = list(map(int, sys.stdin.readline().split()))
    area.append(now_list)
    max_height = max(max_height, max(now_list))

dirr = [-1,1,0,0]
dirc = [0,0,-1,1]

def dfs(row, col ) :
    for i in range(4) : 
        tmpr, tmpc = row+dirr[i], col+dirc[i]
        if 0<=tmpr<N and 0<=tmpc<N and area[tmpr][tmpc]!=-1 and visited[tmpr][tmpc]==0 : 
            visited[tmpr][tmpc] = 1
            dfs(tmpr, tmpc )

def count_safe_area(area ) : 
    cnt = 0
    for i in range(N) :
        for j in range(N) :
            # 방문안했으며 잠기지 않는 아이를 발견했으면 
            if visited[i][j]==0 and area[i][j]!=-1 : 
                visited[i][j] = 1 # 방문 처리 해주고
                cnt+=1 # 현재 아이의 영역을 dfs 로 구할 때마다 영역 하나씩 찾는 것임 
                dfs(i,j)
    return cnt

# 장마철에 내리는 비의 양에 따라서 
for rain in range(1, max_height) : 
    # 비에 잠긴 곳은 -1 처리 
    visited = [ [0 for _ in range(N+1)] for _ in range(N+1) ]
    for r in range(N) :
        for c in range(N) : 
            if area[r][c]!=-1 and area[r][c]<=rain : 
                # 잠기지 않았고, 높이가 rain 높이보다 낮으면 잠김 처리
                area[r][c] = -1 # 잠김 표시는 -1로 처리해준다.
    answer = max(answer, count_safe_area(area))

print(answer)

(2) BFS - 73%에서 틀렸습니다.

# https://www.acmicpc.net/problem/2468 안전 영역
from collections import deque
import sys
sys.setrecursionlimit(10**5)
# 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사
N = int(sys.stdin.readline().rstrip())
area = []
max_height = -1
answer = 0

for i in range(N) : 
    now_list = list(map(int, sys.stdin.readline().split()))
    area.append(now_list)
    max_height = max(max_height, max(now_list))

dirr = [-1,1,0,0]
dirc = [0,0,-1,1]

def bfs(row, col ) :
    q = deque()
    q.append((row,col))
    while q : 
        nowr, nowc = q.popleft()
        for i in range(4) : 
            tmpr, tmpc = nowr+dirr[i], nowc+dirc[i]
            if 0<=tmpr<N and 0<=tmpc<N and area[tmpr][tmpc]!=-1 and visited[tmpr][tmpc]==0 : 
                visited[tmpr][tmpc] = 1
                q.append((tmpr, tmpc))

def count_safe_area(area ) : 
    cnt = 0
    for i in range(N) :
        for j in range(N) :
            # 방문안했으며 잠기지 않는 아이를 발견했으면 
            if visited[i][j]==0 and area[i][j]!=-1 : 
                visited[i][j] = 1 # 방문 처리 해주고
                cnt+=1 # 현재 아이의 영역을 dfs 로 구할 때마다 영역 하나씩 찾는 것임 
                bfs(i,j)
    return cnt

# 장마철에 내리는 비의 양에 따라서 
for rain in range(1, max_height+1) : 
    # 비에 잠긴 곳은 -1 처리 
    visited = [ [0 for _ in range(N+1)] for _ in range(N+1) ]
    for r in range(N) :
        for c in range(N) : 
            if area[r][c]!=-1 and area[r][c]<=rain : 
                # 잠기지 않았고, 높이가 rain 높이보다 낮으면 잠김 처리
                area[r][c] = -1 # 잠김 표시는 -1로 처리해준다.
    answer = max(answer, count_safe_area(area))

print(answer)

비 높이가 1부터 시작한다고 생각했는데, 비가 오지 않는 0부터도 생각해줬어야 했다!

< 문제 코드 >

for rain in range(1, max_height+1) :

for rain in range(0, max_height+1) : 
# 비 높이가 1부터 시작한다고 생각했는데, 
# 비가 오지 않는 0부터도 생각해줬어야 했다! 

<반성 점>

• 비가 오지 않는 경우를 캐치하지 못한게 아쉽다 !

<배운 점>

• dfs, bfs 의 복습 !