[SW Expert Academy] 1215. 회문1

1215. 회문1

---

문제)

 

"기러기" 또는 "level" 과 같이 거꾸로 읽어도 앞에서부터 읽은 것과 같은 문장이나 낱말을 회문(回文, palindrome)이라 한다.

주어진 8x8 평면 글자판에서 가로, 세로를 모두 보아 제시된 길이를 가진 회문의 총 개수를 구하는 문제이다.

 

 

위와 같은 글자판이 주어졌을 때, 길이가 5인 회문은 붉은색 테두리로 표시된 4개가 있으며 따라서 4를 반환하면 된다.


[제약 사항]

각 칸의 들어가는 글자는 c언어 char type으로 주어지며 'A', 'B', 'C' 중 하나이다.

글자 판은 무조건 정사각형으로 주어진다.

ABA도 회문이며, ABBA도 회문이다. A또한 길이 1짜리 회문이다.

가로, 세로 각각에 대해서 직선으로만 판단한다.

즉, 아래 예에서 노란색 경로를 따라가면 길이 7짜리 회문이 되지만 직선이 아니기 때문에 인정되지 않는다.

 

 

 

[입력]

각 테스트 케이스의 첫 번째 줄에는 찾아야 하는 회문의 길이가 주어지며, 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트 케이스가 주어진다.


[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 찾은 회문의 개수를 출력한다.

 

 

 

 

풀이)

for _ in range(10):
    n = int(input())
    li = [list(input()) for i in range(8)]
 
    def check(li, n): # 2차원 리스트에서 글자 수가 4개인 회문을 찾는 함수
        answer = 0
        for i in li: # 총 8줄을 돌아야 하므로
            for j in range(8 - n + 1): # 한 줄에서 나올 수 있는 4개짜리 회문
                temp = []
                for k in range(n): # 회문인지 확인해야 할 문장
                    temp.append(i[j + k])
                if temp == temp[::-1]: # 회문이면 answer +1
                    answer += 1
        else:
            return answer
 
    total = 0
    total += check(li, n)
 
    # 전치행렬 만들기
    for i in range(8): # 이유 : 전치행렬을 쓰면 행만 확인하면 되므로
        for j in range(8):
            if i > j:
                li[i][j], li[j][i] = li[j][i], li[i][j]
 
    total += check(li, n)
    print(f"#{_ + 1} {total}")

 

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.