[백준(BOJ)/C++] 24891: 단어 마방진 - 코딩밥상

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

24891번: 단어 마방진

 

• 접근 방법, 논리 흐름(알고리즘)

문제를 보면 길이가 L인 N개의 단어가 주어지는데, 조건을 만족하는 L개의 문자열 배열이 답이 될 수 있는 후보이다.

즉 길이가 L인 L개의 문자열의 배열(L x L)이 후보이다.

여기서 생각한것이, N개의 문자열 중 L개를 뽑아 순서를 바꿔가며 조건을 만족하는 배열을 찾으면 되겠구나 생각했다.

즉 문자열 L개를 순열 방식으로 모든 경우를 돌려(부르트포스) 조건을 만족하는 배열들을 후보로 두고,

후보들을 사전순으로 비교 후에 출력하기로 생각했다.

 

 

• 구현

답이 될 마방진이 사전순 으로 정해지기 때문에 magic문자열 배열을 초기값을 가장 큰 "ZZZZZ"의 배열로 정했다. 

최솟값을 구하는 원리처럼 반복문을 돌린것이다.

check() 함수가 해당 문자열의 배열이 마방진 조건에 부합하는지 판별한다.

이번 스터디 수업에서 배운 재귀를 통해 순열로 모든 경우를 비교하는 방법이 사용된다.

sequence를 층수라고 생각하면 이해가 편한데, 각 층 수 마다 들어갈 수 있는 값들을 반복문으로 돌려준다. (여기서 주의할 점은 이미 포함되어있는 값들을 따로 체크해주어 중복발생을 피한다.)

반복문 중간에 중복을 피하고 재귀로 들어가면 다음층로 이동한다. 

그 다음층에서도 반복문을 돌리게 되고 이 과정이 반복되다가 내가 원하는 층수에 안전하게 도달하게 되면(return 조건) 과정을 수행하고 재귀를 빠져나온다(return).

이 때 return으로 재귀의 전 단계의 함수의 반복문으로 걸리게되고 다음 경우를 탐색한다. 이 과정을 반복하면 모든 경우의 수를 탐색하는것이 된다.

 

다시 문제로 넘어가서, 층수가 완성이 되면(sequence == L) check함수를 통해 마방진인지 확인하고,

만약 마방진일 경우 기존의 마방진과 사전순으로 비교하여 최신화하였다. 사전순 비교하는 방법에서 좀 더 나은 방법이 있을거 같지만, 우선 나의 실력으로는 각 문자열 배열의 처음부터 비교하는 방식으로 하였다. 

만약 마방진을 만들 수 있는 경우가 아예 없을 경우 NONE을 출력해야하니까 possible변수도 따로 체크해주었다.