[백준] 2468 - 안전 영역 (파이썬, Python)

key point🍀 2차원 리스트에서 최대값 구하는 방법!!

1. 리스트를 받아온다.
2. 이 때 각 행들에서 중복 요소 없이 숫자들을 num_list에 받아옴. 이 숫자들을 for 문을 활용하여 bfs 탐색을 할 것임.
3. 각 높이에 따라 for문을 실행함.
4. 우선 방문 체크를 할 visited 리스트 필요.
5. arr 리스트를 돌며 해당 높이보다 낮은 높이들은 방문처리 함.
6. 이후 영역 갯수를 확인하기 위해 bfs 탐색을 함.
7. 탐색이 끝난 후 영역의 갯수를 result라는 set에 넣어 줌.
8. 🥦 여기서 주의할 점은!!!! 모든 지역의 높이가 같다면 답은 0이 아니라 1이라는 것!! 여기서 에러가 떴었다. 암튼 에러를 쉽게 찾을 수 있어서 좋았다.

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

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def bfs(x,y):

    queue = deque([(x,y)])
    visited[x][y] = 0

    while queue:
        r, c = queue.popleft()

        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]

            if 0 <= nr < n and 0 <= nc < n:
                if visited[nr][nc] == 123:
                    queue.append((nr,nc))
                    visited[nr][nc] = 0


n = int(input())
arr = []
num_list = set()
for _ in range(n):
    tmp = list(map(int, input().split()))
    arr.append(tmp)
    for i in tmp:
        num_list.add(i)


## 높이에 따라 방문 쳌하고 dfs돌기
result = set()
for num in num_list:
    visited = [[123]*n for _ in range(n)]
    ## 높이가 num이하이면 방문쳌 0으로 변경
    for i in range(n):
        for j in range(n):
            if arr[i][j] <= num:
                visited[i][j] = 0
    cnt = 0
    ## 해당 영역을 bfs 탐색
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 123:
                bfs(i,j)
                cnt += 1

    ## 영역의 갯수들을 result에 담아두기
    result.add(cnt)

##### 모든 지역의 높이가 같은 경우는 답이 0이 아닌 1이다.
answer = max(result)
if answer == 0:
    print(1)
else:
    print(answer)

나는 방문체크 후 bfs 탐색으로 풀었지만
풀이들을 읽어보니
dfs를 사용하고 해당 높이 이하인 아이들을 체크할 필요 없이 해당 높이 이상인 아이들만 dfs 탐색을 해도 되더라~~
고 방식으로 한번 풀어봐야겠다🍰

🥑 2차원에서 max값 출력하는 방법

6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7
요러한 2차원 리스트가 있다고 가정하자.

arr = [list(map(int, input().split()) for _ in range(n)]
print(arr)
--> [[6, 8, 2, 6, 2], [3, 2, 3, 4, 6], [6, 7, 3, 3, 2], [7, 2, 5, 3, 6], [8, 9, 5, 2, 7]]

print(list(map(max,arr))) --> 각 리스트의 max값들!!!!!!!
--> [8, 6, 7, 7, 9]

print(max(map(max,arr))) --> 각 행의 max값들 중 가장 큰 값 
--> 9

프로젝트 하느라 알고리즘에게 무신경했다. 미안해!
알고리즘 다시 푸니 꽤나 재밌다.

## 아침에 dfs로 다시 풀어봄.


sys.setrecursionlimit(100000)

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def dfs(x, y):

    visited[x][y] = 1

    for i in range(4):
        nr = x + dr[i]
        nc = y + dc[i]

        if 0 <= nr < n and 0 <= nc < n:
            if arr[nr][nc] > num and not visited[nr][nc]:
                dfs(nr, nc)

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
num_range = max(map(max, arr))                              ## 2차원 리스트에서 max값 찾는 방법 (각 행에서 최대값을 찾은 후 그 값들 중의 최대값을 찾기)
result = 0

for num in range(num_range):
    visited = [[0]*n for _ in range(n)]
    cnt = 0
    for i in range(n):
        for j in range(n):
            if arr[i][j] > num and visited[i][j] == 0:      ## 해당 높이 이상인 요소들을 dfs탐색하기
                dfs(i, j)
                cnt += 1
    result = max(result, cnt)

print(result)