BOGGLE 보글 게임 / ALGOSPOT
문제링크 : https://algospot.com/judge/problem/read/BOGGLE
제출링크 : https://algospot.com/judge/submission/detail/653737
자바소스 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/BOGGLE/src/Main.java
DP로 풀어야 하는 문제입니다. exhaustive search 전부다 찾으면, 시간이 너무 오래 걸림니다.
게임판이 모두 a 로 채워저 있고, 찾아야하는 단어가 aaaaab 라고 한다면,
- exhaustive search로 찾을 때, 모든 칸을 방문합니다.
- 마지막에 b 가 없어서 찾지 못하고, NO를 출력합니다.
문제 처음에 풀때, Recurrence relation를 어떻게 잡아야 하는지 고민을 좀 했었던 문제입니다.
게임판의 크기 : M x N 이라고 하면
게임판의 (0, 0)에서 처음으로 찾을 때는, exhaustive search 방법으로 찾는 것과 동일합니다.
하지만, (0,1)에서 (0,0)에서 방문했던 곳을 또 방문할 필요는 없습니다.
이렇게 하기 위해서는 아래와 같이 recurrence relation을 정의할 수 있습니다.
dp_{i,j,k} = k
단어의 K번째 글짜를 지나갈 때, 게임판의 (i,j) 방문했다.
이렇게 정의 하기 위해서는 dp는 M x N x '단어의 길이' 크기의 DP 배열이 이어야 합니다.
이제 부터는 방문하기 전에, dp 를 먼저 확인해 볼 필요가 있습니다.
dp_{i,j,k}가 0 인 위치만 방문하고, 0이 아닌 숫자가 있다고, 방문하려고 했던 순서가, k번 인대, 이미 한번 방문했던 곳이기 때문에, 방문하지 않습니다.
이런 식으로 DP를 사용하면, 중복된 방문을 줄일 수 있기 때문에, exhaustive search보다 빠른 속도로 탐색이 가능합니다.
게임판 모두 a로 채워저 있고, 단어가 aaaab라고 한다면, 위의 그림 처럼, (0,0)에서 시작해서 (1,0)을 지나 (2,0)으로 지나갈 수 있습니다. 지나간 위치와, 순서에 따라서, dp에는 아래와 같이 지나간 순서가 남게 됩니다.
- dp_{0,0,0} = 0
- dp_{1,0,1} = 1
- dp_{2,0,2} = 2
이제 (2,0)에서 다시 aaaab를 찾기 시작한다고 하고, (1,0)을 방문하기 위해서, dp_{1,0,1} 을 방문해 봤더니, 1로 적혀있습니다.
따라서 방문할 필요가 없습니다. 이런 식으로 DP를 사용하면, 중복해서 방문하는 횟수를 줄 일 수 있습니다.
최초에 (0,0)에서 찾는 횟수는 DP를 사용하더라도, exhaustive search 와 동일합니다만, 이후 (1,0)에서 출발하는 경우 부터는 (0,1)에서 방문했던 곳들은 중복 방문하지 않게 되면서, exhaustive search보다 빠른 속도로 탐색이 가능합니다.
이 문제를 해결하기 위한 점화식을 정의할 때, '답을 찾았다/못 찾았다가 아니라', '단어의 몇번째 글자에서 방문했었다' 로 점화식을 정의해서, 3차원 배열로 방문했던 순서를 기록해 두는 것이 이 문제를 해결하는대 있어 가장 중요한 점 입니다.
import java.io.*;
import java.util.Scanner;
/**
* BOGGLE 보글 게임 / ALGOSPOT
* 문제링크 : https://algospot.com/judge/problem/read/BOGGLE
* 제출링크 : https://algospot.com/judge/submission/detail/653737
*/
public class Main {
public static void main(String[] args) throws IOException {
Main main = new Main();
main.getInput();
}
public void getInput() throws IOException {
// Scanner sc = new Scanner(System.in);
Reader sc = new Reader();
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = sc.nextInt();
// sc.nextLine();
for(int t=0; t<T; ++t) {
char[][] map = new char[5][5];
int M = 5;
int N = 5;
for(int i=0; i<M; ++i) {
String line = sc.nextLine();
for(int j=0; j<N; ++j) {
map[i][j] = line.charAt(j);
}
}
int cntWords = sc.nextInt();
String[] words = new String[cntWords];
// sc.nextLine();
for(int i=0; i<cntWords; ++i) {
String word = sc.nextLine();
boolean b = findWord(map, M, N, word, 0);
// System.out.printf("%s %s\n", word, (b)? "YES": "NO");
String ans = word + " ";
ans += (b)? "YES": "NO";
ans += "\n";
bw.write(ans);
}
}
bw.close();
}
public boolean findWord(char[][] map, int M, int N, String word, int idxWord) {
boolean[][][] visitiedMap = new boolean[M][N][word.length()];
for(int i=0; i<M; ++i) {
for(int j=0; j<N; ++j) {
if(findWord2(map, M, N, i, j, word, idxWord, visitiedMap))
return true;
}
}
return false;
}
public boolean findWord2(char[][] map, int M, int N, int i, int j, String word, int idxChar, boolean[][][] visitedMap) {
int[] dis = new int[]{-1, -1, -1, 0, 1, 1, 1, 0};
int[] djs = new int[]{-1, 0, 1, 1, 1, 0, -1, -1};
visitedMap[i][j][idxChar] = true;
if(word.charAt(idxChar) != map[i][j])
return false;
if(idxChar == (word.length()-1))
return true;
for(int k=0; k<dis.length; ++k) {
int di = i + dis[k];
int dj = j + djs[k];
if((0<= di) && (di < M) && (0<=dj) && (dj < N)) {
if(visitedMap[di][dj][idxChar+1]) {
continue;
}
if(findWord2(map, M, N, di, dj, word, idxChar+1, visitedMap))
return true;
}
}
return false;
}
// https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
class Reader
{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader()
{
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException
{
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String nextLine() throws IOException
{
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1)
{
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException
{
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do
{
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException
{
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException
{
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (c == '.')
{
while ((c = read()) >= '0' && c <= '9')
{
ret += (c - '0') / (div *= 10);
}
}
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException
{
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException
{
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException
{
if (din == null)
return;
din.close();
}
}
}