알고스팟(algospot): 보글 게임(BOGGLE) [C++]

문제 출처: www.algospot.com/judge/problem/read/BOGGLE

algospot.com :: BOGGLE

1. 코드

	#include <stdio.h>
	#include <iostream>
	#include <cstring>
	using namespace std;
	char board[5][5]; // 게임 보드판 알파벳 배열
	char word[10]; // 키워드 입력 배열
	int check[5][5][10]; // 글자별 확인여부 체크 [ x 좌표 ] [ y 좌표 ] [ 글자의 위치 ]
	int word_len; // 키워드의 길이
	const int dx[8] = { -1,-1,-1, 0, 1, 1, 1, 0 }; // ↖ 방향부터 시계 방향으로 진행
	const int dy[8] = { -1, 0, 1, 1, 1, 0,-1,-1 };
	int solution(int x, int y, int ptr)
	{
	if (x < 0 || x >= 5 || y < 0 || y >= 5) return 0; // 범위 초과시 실패
	if (check[x][y][ptr]) return 0; // 이미 확인한 것이면 실패
	check[x][y][ptr] = 1; // 확인하지 않았으므로 1로 초기화
	if (board[x][y] != word[ptr]) return 0; // 보드판의 글자와 키워드의 해당 글자가 일치하지않으면 실패
	if (ptr == word_len - 1) return 1; // 바로 위에서 글자 검사에서 통과했기에 글자의 마지막 위치라면 성공
	for (int i = 0; i < 8; i++) //인접한 8칸 검사
	{
	int result = solution(x + dx[i], y + dy[i], ptr + 1); // ↖ 방향부터 시계 방향으로 진행
	if (result) return 1; // 참이라면 성공
	}
	return 0; // 거짓이라면 실패
	}
	int main(void)
	{
	int test_case;
	cin >> test_case;
	while (test_case--)
	{
	memset(board, 0, sizeof(board)); // board의 배열을 0으로 초기화
	for (int i = 0; i < 5; i++) cin >> board[i];
	int word_num;
	cin >> word_num;
	while (word_num--)
	{
	memset(check, 0, sizeof(check)); // check의 배열을 0으로 초기화
	cin >> word;
	word_len = strlen(word);
	int out = 0; // 중첩 반복문 빠져나오는 키워드
	for (int i = 0; i < 5; i++)
	{
	for (int j = 0; j < 5; j++)
	{
	if (solution(i, j, 0))
	{
	out = 1;
	break;
	}
	}
	if (out) break;
	}
	if (out) printf("%s YES\n", word);
	else printf("%s NO\n", word);
	}
	}
	return 0;
	}

view raw Boggle.cpp hosted with ❤ by GitHub

(실행)

 

2. 풀이

이 문제는 반복문으로 풀 수 있겠지만 그렇게 된다면 코드가 굉장히 난잡하게 되거나 알아볼 수 없게 되기 때문에 재귀 함수로 구성하였다. 그리고 조건문은 다음과 같다.

범위 초과할 경우, 이미 확인한 경우, 보드판과 글자가 일치하는지, 그리고 인접한 8칸 검사를 할 때 성공적으로 1이 나오는지 등의 경우를 확인했는데 이 조건들을 생각하는 것이 매우 힘들었다. 그리고 인접한 8칸을 검사할 때는 미리 만들어진 dx와 dy배열의 값을 x와 y에 값을 더함으로써 ↖방향부터 시계 방향으로 검사를 하는 방식으로 되어있다.

인접한 8칸

기존에 알고 있던 x좌표와 y좌표와 다르다고 느낄 수 있지만 이것은 배열의 좌표 기준이다. 그렇기에 이렇게 구성된다.

 

3. 느낀 점

printf 대신에 cout를 쓰려고 했지만 이해도가 낮은 건지 무언가 잘못하고 있는지 모르겠지만 cout을 사용하면 계속해서 답이 틀렸다고 나와서 cout대신 printf를 사용했다. 다음에는 조금 더 이해를 보고 cout을 적용해봐야겠다. 그리고 이걸 풀면서 재귀 함수의 공부가 중요하다는 것을 새삼스럽게 깨달았다. 천천히 꾸준히 노력해야겠다.