BOJ 2186 - 문자판

문제 링크

---

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

문제 해결

---

 1. 임의의 칸에서 시작해서 상하좌우로 1~K만큼씩 움직일 때마다 만나는 문자를 차례로 이었을 때, 주어진 문자열과 같은 경우의 수를 구하는 문제.

 2. DP[i][j][k] = 문자판 좌표 (i, j)에 있는 문자와 주어진 문자열 S의 S[k]와 같을 때의 경우의 수.

주의할 점 || 생각해볼 점

---

 1. DP 테이블을 만들 때, k의 범위가 최대 80까지임을 간과하면, 많은 수의 "틀렸습니다"를 획득할 수 있다.

 2. BFS, DFS 모두 해를 구할 수 있다. 하지만 BFS로 문제를 해결할 시 메모리 초과에 걸리게 되어서 DFS+DP로 구현했다.

참고

---

 - 

※ 정확하고 부드러운 태클은 언제나 환영입니다.