[백준 알고리즘] 2468번 안전 영역. 파이썬(python)

오답1)

1

5

위의 입력이 주어졌을 때, 

print(max(safe_area))
ValueError: max() arg is an empty sequence

리스트의 값이 비어있어 max함수를 사용할 수 없게 된다.

그래서 safe_area=[]에서 safe_area=[0]로 초기화를 바꿔줬다.

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

n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
min_n=1e9
max_n=-1e9

for i in a:
    if min_n>min(i):
        min_n=min(i)
    if max_n<max(i):
        max_n=max(i)

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

def bfs(x,y):
    global cnt
    q=deque()
    q.append((x,y))
    v[x][y]=1

    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<n:
                if a[nx][ny]>m and v[nx][ny]==0:
                    v[nx][ny]=1
                    q.append((nx,ny))

safe_area=[] 
for m in range(min_n,max_n):
    cnt=0
    v=[[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if a[i][j]>m and v[i][j]==0:
                bfs(i,j)
                cnt+=1
    safe_area.append(cnt)

print(max(safe_area))# 지역의 높이가 다 같을 경우 비어있어서 max값을 찾을 수 없음

 

 

 

오답2)

비가 온 높이 설정을 지역 높이의 최솟값~최댓값으로 지정했다.

그런데 비가 아예 안 왔을 경우를 고려해야 해서 0~최댓값으로 변경했다.

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

n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
min_n=1e9
max_n=-1e9
for i in a:
    if min_n>min(i):
        min_n=min(i)
    if max_n<max(i):
        max_n=max(i)

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

def bfs(x,y):
    global cnt
    q=deque()
    q.append((x,y))
    v[x][y]=1

    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<n:
                if a[nx][ny]>m and v[nx][ny]==0:
                    v[nx][ny]=1
                    q.append((nx,ny))

safe_area=[0]
for m in range(min_n,max_n):
    cnt=0
    v=[[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if a[i][j]>m and v[i][j]==0:
                bfs(i,j)
                cnt+=1
    safe_area.append(cnt)

print(max(safe_area))

 

 

정답)

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

n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]

max_n=-1e9
for i in a: # 최대 높이 찾기
    if max_n<max(i):
        max_n=max(i)

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

def bfs(x,y):
    q=deque()
    q.append((x,y))
    v[x][y]=1

    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<n: # 범위를 벗어나지 않고
                if a[nx][ny]>m and v[nx][ny]==0: # 비가 온 높이보다 높으면서 방문하지 않은 곳
                    v[nx][ny]=1
                    q.append((nx,ny))

safe_area=[0]
for m in range(0,max_n): # 비가 오지 않는 경우를 고려해 0부터 최대 높이까지
    cnt=0
    v=[[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if a[i][j]>m and v[i][j]==0:
                bfs(i,j)
                cnt+=1
    safe_area.append(cnt)


print(max(safe_area))