파이썬 백준 2468번 : 안전 영역

문제 

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

2468번: 안전 영역

 

풀이

DFS를 활용해서 풀었다. 

x,y 좌표값으로 DFS를 수행하면서 처음 방문되는 경우 안전지대의 개수를 증가시킨다.

DFS 수행시 상,하,좌,우로 연결되어있는 값이 안전지대이면 방문처리한다. (따라서 연결되어있는 방문지대가 여러번 count되지 않는다.)

비의 양은 지대 높이의 최댓값까지 반복하면서 어느 지점일 때 안전지대가 가장 많이 생기는지 판단한다. 

import sys
sys.setrecursionlimit(100000)

def DFS(Graph,x,y,N,H):
    if x<=-1 or x>=N or y <=-1 or y>=N: # 범위를 벗어나면 False를 반환한다
        return False
    if Graph[x][y]>H: # 물에차는 높이보다 높으면 안전영역으로 분류한다
        Graph[x][y]=-1 # visited=True와 같은 의미
        DFS(Graph,x-1,y,N,H) # 상, 하, 좌, 우 에 대해 호출되는 내용들은 반환값을 사용하지 않음 -> 연결된 모든 노드를 방문처리하는 용도  
        DFS(Graph,x,y-1,N,H)
        DFS(Graph,x+1,y,N,H)
        DFS(Graph,x,y+1,N,H)
        return True
    return False

if __name__ == "__main__":
    N=int(sys.stdin.readline())

    Graph=[]
    for i in range(N):
        Graph.append(list(map(int,sys.stdin.readline().split(' '))))
    H=0
    max_height=max(map(max,Graph)) # 그래프의 높이의 최댓값
    max_result=0 #출력 할 안전영역의 최대 갯수
    while H<=max_height: # 그래프 높이의 최댓값보다 크지 않을때까지 반복한다
        temp_Graph = [row[:] for row in Graph] #Graph값을 temp_Graph에 저장
        result=0
        for i in range(N):
            for j in range(N):
                if DFS(temp_Graph,i,j,N,H)==True: #방문처리가 되었다면 count
                    result+=1 #안전지대의 개수 세기

        if max_result<result: #안전지대의 최대개수 업데이트
            max_result=result 
        H+=1 #높이 증가
    print(max_result)

 

 

 

덧)

😣 재귀의 깊이를 설정해주지 않으니 런타임에러가 발생했다. 

재귀를 사용해서 풀어야하는 문제에는 필수적으로 아래 코드를 써야한다. 

sys.setrecursionlimit(100000)

 

 

🤔 80%정도에 계속 틀려서 확인해보니 max_height 설정의 문제였다. 

max_height=max(max(Graph))

위와 같이 선언 하면 처음에 해당 배열에서 원소값의 합이 최대인 행을 찾기때문에 잘못된 값을 반환한다.

따라서 이차원배열에서 최댓값을 찾으려면 아래와 같이 사용해야한다. 

max_height=max(map(max,Graph))

 

😯

Graph를 복사할때 temp_Graph =Graph를 사용하면 결국 같은 주소를 가르키게 되어, temp_Graph의 변경사항이 Graph에 전달된다.

temp_Graph = [row[:] for row in Graph]

위와 같이 복사해서 사용해야한다.