[백준 2468번-안전영역]-파이썬

백준 2468번 파이썬 풀이

<문제>

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

<풀이>-DFS알고리즘 사용, 중복제거/max(map(max,2차원리스트)))

키포인트 :  장마철 내리는 비의 양을 설정하는 방법

1) 그래프에 나타나는 높이정보를 기준으로 비의 양을 설정한다. 이때 중복값을 제거하기 위해 set함수를 사용한다.

height = []
graph = []
for _ in range(n):
    data = list(map(int,r().split()))
    for i in data:
        if i not in height:
            height.append(i)
    graph.append(data)

<코드설명>

graph의 높이정보를 list형태로 입력받는다.(data = list(map(int,input().split()))

입력받은 list에서 중복값을 제거해 height배열(높이정보 저장하는 배열)에 저장한다.

 

2) 그래프에 나타나는 높이정보중 최댓값을 기준으로 0~최댓값까지의 값을 기준으로 안전영역을 계산한다. 

for k in range(max(map(max,graph))):

<코드설명>

2차원 리스트에서 최댓값을 구하는 방법 :  max(map(max,graph))

 

※주의※ :  단순히 max(2차원리스트)를 하게 되면 2차원리스트의 합이 가장큰 행을 출력하게 된다.

 

따라서 k값을 0부터 (최댓값-1)까지 설정함으로써 안전영의 크기를 각각 구할 수 있다.

 

<코드>-파이썬

import sys
sys.setrecursionlimit(100000)
r = sys.stdin.readline
dx = [-1,0,1,0]
dy = [0,-1,0,1]
def dfs(x,y,h):
    visited[x][y] = True
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if (0<=nx<n) and (0<=ny<n) and not visited[nx][ny] and graph[nx][ny]>h:
            dfs(nx,ny,h)

n = int(r())
height = []
graph = []
for _ in range(n):
    data = list(map(int,r().split()))
    for i in data:
        if i not in height:
            height.append(i)
    graph.append(data)
ans = 1
for k in height: #for k in range(max(map(max,graph))):
    count = 0
    visited = [[False]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if graph[i][j]>k and not visited[i][j]:
                count+=1
                dfs(i,j,k)
    ans = max(ans,count)
print(ans)