[백준] 1949번: 우수 마을 - 파이썬

문제 보기

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

1949번: 우수 마을

 

 

 

 

---

 

풀이 및 코드

 

필자는 dfs, bfs를 통한 탐색을 할 때 재귀 깊이 에러 때문에 재귀함수보다는 deque를 이용해 문제를 해결하고자 했다. 근데 오늘 이 문제는 재귀를 이용한 방법이 가장 맞는 듯했다. 하지만 n의 범위가 10000이기에 재귀에러가 발생할 수밖에 없었다. 

 

sys.setrecursionlimit(10 ** 5)

 사실 이 메서드를 모르는 것은 아니었지만, 코테 공부를 처음 시작할 무렵 재귀깊이를 건드리면 안 된다고 생각해 거들떠보지도 않았다. 그런데 구글링에 검색해보니 코테 꿀팁 중에 하나가 해당 메서드라고 한다... 파이썬은 재귀깊이가 비교적 얕아 해당 메서드를 이용해 깊이를 늘려주어야 재귀와 관련된 문제를 풀 수 있다고 한다. 이제라도 알았으니 참 다행이다!

 

 

푸는 방식은 dfs와 dp를 이용해 풀었다.

• dfs로는 연결된 마을들을 돌면서, 해당 마을이 우수 마을일 경우, 아닐 경우를 나누어 각각 dp에 저장했다.
• dp는 dp[마을 번호][우수 마을 여부] 형태로 구성했다.
• 만일 이전의 마을이 우수 마을이었다면 다음 마을은 무조건 우수 마을이 아니다.
• 만일 이전의 마을이 우수 마을이 아니라면 해당 마을은 우수 마을과 비 우수 마을 모두 가능하다. (문제에서는 우수마을이 아닌 경우 우수마을이 인접해야 한다고 하였지만 우수x - 우수x - 우수x 가 된다면 총합이 최대가 될 수 없기에 결과적으론 무관하다)