[백준] 2186번: 문자판 - 파이썬

문제보기

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

2186번: 문자판

 

 

 

 

---

 

풀이 및 코드

 

해당 문제는 dfs와 dp를 이용해 푸는 문제로, solved.ac에 골드 3으로 랭크되어 있다.

 

 

 

""" 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다. """

 

 

문제를 보면 n, m은 100이하 k는 5이하로 숫자가 작아보여 dfs만을 사용해 구현했지만 시간 초과로 틀렸다.

 

 

""" 첫째 줄에 경로의 개수를 출력한다. 이 값은 2^31-1보다 작거나 같다. """

 

 

출력을 보니 입력값이 작지 않다! 해당 문제는 memorization를 사용해서 푸는 문제였다ㅎㅎㅎ (요즘 대부분 문제를 한두번씩 틀리고 맞춘다. 문제를 꼼꼼히 보는 연습이 필요해 보인다)

 

 

필자는 i번째 문자열을 찾기 위해 (y, x) 위치를 방문했을 때 문자열을 완성할 경우의 수를 dp라는 배열에 저장했다. dfs를 진행하다 보면 필요한 문자열을 가지고 있는 특정 좌표들만 계속하게 방문하게 된다. 따라서 해당 위치를 지나갔을 때 완성할 수 있는 경우의 수를 저장해 놓는다면, 다음 문자열 찾기 반복을 효과적으로 줄일 수 있다. 또한 성공 할 때만 저장한다면 단어의 마지막 문자열 직전까지만 만들 수 있는 경우에는 많은 시간이 낭비된다. 따라서 성공 여부를 떠나 i번째에 해당 위치에 방문했을 때 도출되는 값을 저장해주었다.