[KOISTUDY] [017D] [381] 격자 읽기

2014. 2. 25. 13:46알고리즘 문제풀기/각종 OJ 풀이

http://koistudy.net/?mid=prob_page&NO=381

간단한 boggle 게임이다.


아래와 같은 격자판을 보자.



위 격자판에서 TARTU를 읽는 방법의 수는 7가지가 있다.



알파벳 대문자로만 이루어진 문자 격자판과 단어가 주어질 때,

그 단어를 읽는 방법의 수를 구하는 프로그램을 작성하시오. 


이전 문자와 가로, 세로, 대각선으로 연결된 것들만 읽을 수 있다.


(가로, 세로 높이 ≤ 200, 문자열길이 ≤ 100,

답 ≤ 1018 )


해법)


1)

백트래킹 방식으로 모든 문자열을 찾다.

시간복잡도는 최대 문자열의 수만큼 나온다.

그런데 답이 10^18 이하라는 말은 최대 10^18정도의 답도 나올 수도 있다는 것.


2)

위의 방법과 비슷하게 다이나믹 프로그래밍을 이용한다. (backtracking을 memoization하는 것으로 생각해도 된다)

배열 dyn[h][w][l]를 선언한다.

dyn[i][j][k]=문자열의 k번째 까지 읽어서 (i,j) 칸의 문자에서 끝나는 방법의 수

그러면 문자열의 k번째 문자를 찾기 위해서 H×W의 격자를 돌아다녀야 하므로,

Naive O((HW)^L).

그런데, 우리는 일반적으로 변하지 않는 건 한번 탐색으로 끝낸다.

예를 들어, 도서관에서 책들을 찾을때 원하는 책 하나하나마다 도서관 전체를 뒤지는게 아니라,

원하는 책 목록을 두고, 도서관을 한 번 돌면서 목록에 일치하는 책을 볼때마다

한 권 한 권 꺼내는 것.

마찬가지로, 우리가 격자에서 A를 찾고싶다고 A만 찾고, B를 찾고싶다고 B만 찾는 것이 아니라,

전체를 돌면서 각각의 알파벳이 어느 위치에 있는지 목록을 기록해두면 된다다.

이렇게 하면 처음에 H×W만큼 탐색한 후,

각각의 알파벳이 들어있는 격자만 바로 보면 된다.

'알고리즘 문제풀기 > 각종 OJ 풀이' 카테고리의 다른 글

AtCoder  (0) 2016.09.04
나코더 방학 연습 2주차 풀이  (0) 2016.08.07
나코더 방학 연습 1주차 풀이  (0) 2016.07.28
1591: 수열 복원  (0) 2016.03.08
[algospot] [NUMB3RS] 두니발 박사의 탈옥  (0) 2014.05.30