백준 - 2468 | [dfs/bfs] | 안전영역 (feat. Python)

출처

2468 안전영역 문제

목표 (출력)

여기서 말하는 안전영역은 상하좌우 물에 잠기지 않은 인접영역 하나씩을 말한다.
비가 얼마나 올지 모르지만 아래의 그래프의 예시에서 비가 높이 별로 다양하게 왔을 경우를 상상해, 안전영역의 갯수가 최대인 상황일 때 해당 갯수를 출력해라

🛑예시) n= 5인 지역 높이 정보

이 그래프를 높이가 4이하의 모든 지점들이 물에 잠겼다고 가정했을 경우 그래프는 이렇다.

가능한 안전영역(흰색) = 5개

---

⚡ 문제에서 중요한 부분

• 비가 얼마나 올지 모른다 -> 비는 우선 현재 정해진 n의 높이까지가 최대 높이로 올 수 있는 것
• 비는 아무리 와도 최대 높이(n)까지 올 수 있다.
  => 그렇다고 n만큼 오면 모두 잠기기 때문에 n-1까지만 계산
• 메모: "아무 지역도 물에 잠기지 않을 수도 있다."
  => 우리는 비가 안 오는 0의 경우도 생각해야 한다.

---

❌ 어떻게 접근해야 풀렸을까?

1. 내가 접근한 방식과 실수

bfs를 통해서 수중 높이가 t일 때마다 나올 수 있는 인접영역들의 갯수(안전영역)을 세서 일일히 MAX 값과 비교해주려고 함

이 때 발생한 문제

1. visited로 방문리스트를 따로 생성하지 않았다.
   • 그대신 graph에 일일히 0으로 방문처리를 하였다.
     -> 이로써 t의 값이 올라갈 때마다 graph 리스트에 다시 처음 상태로 초기화 되어 있어야 했는데 그러지 못했다.

2. 문제를 풀며 새로이 알게된 부분

하지만 이 부분은 visited 리스트를 생성 후 저 곳에서 초기화 하면 해결이 가능한 부분이였다.

• 내 접근도 괜찮았지만 bfs 함수를 풀어왔던 방식을 좀 더 폯 넓게 생각하였다면 접근에 오래 걸리지 않았을 것 같다.

---

🚩 접근해야 하는 방식

현재 물의 수심(t) 보다 높은 애들은 bfs()함수를 통해 안전 영역의 갯수를 counting 해줄 것

• 이제부터 우리는 현재 물의 수심보다 같거나 낮은 경우들은
  -> 방문할 필요가 없다
  -> visited[] = 0으로 생각해준다
• 현재 물의 수심보다

이런 식으로 봐줘야 한다는 것이다.
(검정은 따로 0으로 처리를 못해주었다.. 그림판으로 그리다보니)

🔋 해결한 코드

#[dfs, bfs] 안전영역 (실1)
# 안전한 영역 구하기
# 안전영역: 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접한 영역

# BFS로 풀어야 함
# 가까운 영역을 전부 탐색해서 안전영역의 갯수를 세야함


from collections import deque
import sys
input = sys.stdin.readline


#3. bfs 함수 실행
def bfs(x,y, high):
    que = deque()
    que.append((x,y))
    visited[x][y] = 1 #방문

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

        #상하좌우 방향으로 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 그래프를 영역 밖으로 벗어나지 않게
            if nx <0 or ny < 0 or ny>=n or nx >= n:
                continue

           # 현재 물의 수심과 비교, 방문 전적 x 면 => 동작
            if graph[nx][ny] > high and visited[nx][ny] == 0:
                visited[nx][ny] = 1 #방문처리 함함
                que.append((nx,ny))



# 1. 입력값 받기
n = int(input())
graph = [list(map(int,input().split())) for _ in range(n)]
high = 0

for i in range(n):
    for j in range(n):
        if graph[i][j] > high: #최대 높이값 저장
            high = graph[i][j]

dx = [-1, 1, 0, 0] #상하좌우
dy = [0, 0, -1, 1]


MAX = 0
# 2. 수심이 달라질 때마다 달라지는 안전영역 갯수 비교
for t in range(high):
    visited = [[0] * n  for _ in range(n)]
    cnt = 0 #안전 영역 갯수

    for i in range(n):
        for j in range(n):
            # 해당 칸을 방문한 전적 x, 해당 칸은 수심보다 높음 => bfs실행
            #bfs 실행으로 인접 영역들을 visited[] 체크해줌
            if graph[i][j] > t and visited[i][j] == 0:
                bfs(i,j,t)
                cnt+=1
    # 4. 해당 수심의 안전영역과 & 현재까지 가장 컸던 안전영역 갯수를 비교
    if MAX < cnt:
        MAX = cnt

print(MAX)