[DFS, 파이썬] 백준 2468. 안전영역

(+) 이차원 배열의 max 찾기

방법 1. 

graph = [list(map(int, input().split())) for _ in range(N)]
graph_min = min(map(min, graph))    # min_height
graph_max = max(map(max, graph))    # max_height

방법 2.

g = []
largest = 0
for _ in range(n):
    l = list(map(int, input().split()))
    largest = max(max(l),largest)
    g.append(l)

 

문제

영역 구하는 문제인데, 물의 수위를 조절하며 영역의 개수가 최대일 때를 찾아야 한다. 예시 답은 다 맞게 나오는데, 백준 저지에서 자꾸 틀린다... 왜지... 

근데 왜 틀렸는 지 모르겠다.

ㅠㅠㅠㅠ

입력이 아래와 같은 경우 답이 오답으로 나온다.

2
1 1
1 1

물 깊이를 1~largest 의 범위로 진행했기 때문이다. 수심이 0일 때, 4개 칸 모두 잠기지 않기 때문에 안잠긴 영역이 1이 나와야 하고, 이후 물 높이가 높아지면 2부터 바로 전체가 잠겨버려 안잠기는 영역이 없어서 0이 나온다. 1이 최대 영역의 수 이므로 출력값이 1로 나와야 한다. 근데 d를 1부터 시작하면 아무리 물의 높이를 바꿔도 전부 잠기는 걸로 나와서, 출력이 0이다.

문제를 여러 번 읽으면서 물 높이에 대한 단서가 없고, 단지가 2~100 의 조건인 줄 알았는데, 단지는 1~ 이었기 때문에 틀렸다.

교훈

내 개발환경에서 입력한 값들이 정답이 나왔어도, 백준 저지에서 틀렸을 때, 입력값을 복잡하게 하기보다 단순하되 경계값에 있거나 극단에 있는 값들로 구성하는 것이 오류를 잡는 데 도움이 된다는 걸 배웠다.

원래 코드

import sys
sys.setrecursionlimit(10**4)
input = sys.stdin.readline

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

g = []
largest = 0
for _ in range(n):
    l = list(map(int, input().split()))
    largest = max(max(l),largest)
    g.append(l)

dx = [1,-1,0,0]
dy = [0,0,1,-1]
visited = [[1]*n for _ in range(n)]

def DFS(vx, vy, d):
    global area
    # 물에 잠기면 나가
    if -1<vx<n and -1<vy<n and visited[vx][vy]==1 and g[vx][vy] > d:
        visited[vx][vy] = 0
        for i in range(4):
            DFS(vx+dx[i], vy+dy[i], d)
        return True
    return False
    
area = 0
d = 1
lst = [0]
while d <= largest:
    for i in range(n):
        for j in range(n):
            if visited[i][j]==1 and DFS(i, j, d) == True:
                area+=1

    lst.append(area)
    d+= 1
    area = 0
    visited = [[1] * n for _ in range(n)]
print(max(lst))

여기서 d = 1 이 아니고, d = 0으로 바꾸면 답이 된다.

 

 

디코딩용 코드

import sys
sys.stdin = open('graph input.txt', 'rt')
input = sys.stdin.readline

n = int(input())

# 그래프 만들
g = []
largest = 0
for _ in range(n):
    l = list(map(int, input().split()))
    largest = max(max(l),largest)
    g.append(l)

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

def DFS(vx, vy, d):
    global area
    # 물에 잠기면 나가
    if -1<vx<n and -1<vy<n and visited[vx][vy]==1 and g[vx][vy] > d:
        visited[vx][vy] = 0
        # print('안잠긴 좌표', vx,vy, end='/ ', sep=',')
        # print('수위', g[vx][vy], '>',d)
        for i in range(4):
            DFS(vx+dx[i], vy+dy[i], d)
        # 근처 4개의 DFS를 돌고 나왔을 때, return True 나오는 횟수를 확인할 수 있음
        # print('point')
        return True
    # print('잠긴 좌표', vx,vy, end='/ ')
    # print('수위', g[vx][vy], '<=',d)
    return False

area = 0
d = 0
lst = [0]
visited = [[1]*n for _ in range(n)]
while d < largest+1 :
    for i in range(n):
        for j in range(n):
            if DFS(i, j, d) == True :
                area+=1
                # print('-- 출발', i,j,d)
                # 이 좌표를 기준으로 인접 칸들을 탐색
    # d에 따른 안 잠긴 영역의 수
    print('수위',d,'일 때 안잠긴 영역 수',area)
    if max(lst) < area:
        lst.append(area)
    d+= 1
    area = 0
    visited = [[1] * n for _ in range(n)]
print(max(lst))

 

정답에서 발전을 위한 수정!

g = []
largest = 0
for _ in range(n):
    l = list(map(int, input().split()))
    largest = max(max(l),largest)
    g.append(l)

 

n = int(input())
g = [list(map(int, input().split())) for _ in  range(n)]
largest = max(map(max, g))
small = min(map(min, g))

print(g)
print(largest)
print(small)