(JAVA) 백준 3967번 : 매직 스타

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

3967번: 매직 스타

 

백트래킹 문제이다.

 

 

풀고 나서 제출 내역들을 보니

 

내가 속도가 다른 사람들에 비해 많이 느리게 나왔다.

 

하지만

 

다른 사람들의 풀이를 보는 것 보다

 

함수를 나눠 설계했기 때문에

 

이해는 쉬울 수 있을 것이다...!!!!

 

 

매커니즘

---

 

우선, 문제를 살펴보면

 

저 빨간 동그라미 부분에 들어갈 알파벳을 구하는 문제이다.

총 12칸이며, 5개 라인의 입력을 통해 초기 설정된 칸과 알파벳을 알 수 있다.

 

 

또한, 세 가지 조건을 충족해야 한다.

 

 1) 각 칸은 중복된 알파벳이 없다.

 2) A부터 L까지 1 ~ 12로 정의한다.

 3) 한 줄에 존재하는 4칸의 알파벳을 더하면 26이 되고, 총 6줄 전부 만족해야 한다.

 

 

 

다음,

 

아이패드로 작성해서 조금 읽기 난해할 수 있다..

 

 

나는 전체 길이가 13인(인덱스 1 ~ 12 사용) 배열을 총 3개를 만들었다.

*** 참고로, 알파벳은 'A' == 65 아스키코드를 참고하여 index = '해당 알파벳' - 64 로 계산해서 진행했다.

ex) A : 65 - 64 = 1(첫 번째는 1이라고 정했으므로 만족)

ex2) B : 66 - 64 = 2

 

1) boolean 배열. 해당 알파벳이 이전 줄 또는 이전 칸에서 사용했는지 여부를 파악하는 배열.

 

2) int 배열 2개.

  2-1) 첫 번째 int 배열은 해당 번째 칸에 들어가는 알파벳(번째) 값이 들어간다.

  2-2) 두 번째 int 배열은 사전순으로 가장 작은 알파벳들을 담는 배열이다. 

 

 

마지막으로,

 

각 줄마다 4개의 칸을 더하면 26이 되는 조건을 판별하기 위해

각 줄에 들어가있는 칸의 인덱스를 별도의 2차원 배열에 담았다. 

 

이를 가지고 위의 int 배열의 인덱스 값만 찾아 더해 계산하면 된다.

 

 

 

 

매커니즘의 단계로 넘어가보자.

 

 

매커니즘

---

 

1. x 또는 . 이 아닌 문자가 들어오면 무조건 초기 알파벳에 해당하므로, 알파벳 - 64 한 값을 int 배열에 넣고, boolean 배열의 인덱스 값을 찾아 true로 변경한다. (해당 알파벳을 사용했기 때문에)

 

 

2. 첫 번째 칸을 파라미터로 하는 백트래킹 함수를 호출한다.

 

 

2-1. 해당 칸에 이미 초기 알파벳이 들어가있으면 다음 칸을 파라미터로 하는 백트래킹 함수 호출

 

2-2. 알파벳 A ~ L(1 ~ 12)를 하나씩 사용해보는 For문을 사용해 아직 사용하지 않은 알파벳을 찾는다.

2-2-2.  찾은 알파벳을 넣은 경우와 넣지 않은 경우를 백트래킹 함수로 표현한다.

 

 

3. 모든 칸에 알파벳을 채우면 모든 줄이 26을 만족하는지 판별한다.

 

 

4. 만족하는 경우 정답

4-1. 만족하지 않으면 다음 경우를 찾으러 돌아간다.

 

 

말은 쉬워보이는데

코드가 길어질 수 밖에 없습니다...

 

저는 함수로 기능을 분리하고

흐름을 파악하기 좀 더 수월하게 작성했기 때문이죠..

 

 

 

이상입니다.

 

 

감사합니다!

 

 

 

소스코드

---