[Python] 백준 2468번 - 안전 영역

알고리즘

ji_iin 2021. 8. 9. 12:49

문제

문제에서 예시를 들어 설명할 때 모든 경우를 다 조사해 보면 이라고 설명되어 있다. 즉, 모든 경우의 수를 조사해야 됨 (이라고 나는 이해했다.)
장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력

< 1차 >

배열을 입력할 때 N 이상인 값들만 방문여부를 True 값으로 바꾸고 깊이우선탐색을 진행한다.
깊이우선탐색을 진행하고 끝날때 안전영역 값(count)을 늘린다.
또 깊이우선탐색을 반복해야하는데 현재 count 값이 < 계산된 count값보다 크다면 종료한다. (즉, 계산된 count값이 클 때까지만 반복)
count값을 출력하고 종료

< 2차 >

1차에서 3번째 줄처럼 할려고 했으나, DP처럼 그전의 경우만 비교해서 모든 경우의 최대라는 보장이 없다.

즉, 모두 확인해야 한다. 그래서 배열의 최대값을 구하고 그 크기만큼 모두 반복해서 확인해야 한다.

자바로 풀다가 파이썬으로 풀어볼려고 하니까 간결해서는 좋은데 문법을 모르겠다.(^^;) 그나마 장고를 썼었어서 아예 낯설지는 않지만, 그래도 시간이 걸렸다.

1차시기 때 풀었던 코드는 그냥 깊이우선탐색의 정석코드인데 거기다가 플러스 2차원 배열의 값 중 최대 값을 기준으로 반복을 돌려야 해서 그 값을 찾는 코드를 모르겠어서 구글링 좀 했다. map 함수를 짚고 넘어가게 되었다.