[Python] 회문1 (SWEA D3 1215번 파이썬)

"기러기", "토마토", "스위스"와 같이 똑바로 읽어도 거꾸로 읽어도 똑같은 문장이나 낱말을 회문(回文, palindrome)이라 한다.

8x8 평면 글자판에서 제시된 길이를 가진 회문의 개수를 구하라.
 

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


[제약 사항]

각 칸의 들어가는 글자는 'A', 'B', 'C' 중 하나이다.

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

가로 또는 세로로 이어진 회문의 개수만 센다.

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

 

[입력]

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

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

[출력]

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

 

 

 

 

다소 까다로운 완전탐색 문제입니다. 팰린드롬류의 문제와 완전탐색이 결합된 형태의 문제인데, 자주 보지 못한 유형인 것 같아서 재미있게 풀었습니다.

 

초기에 동작은 제대로 되는데 답이 계속 틀리게 나와서 왜그럴까 고민하다가, 행과 열을 동시에 판단하려고 하다보니 탐색되지 않는 부분이 있다는 것을 깨달았습니다.

이후 행과 열을 분리해서 탐색하도록 코드를 작성하니 정상적인 작동을 했습니다.

 

코드

# SWEA 회문1
def check(arr: list): #앞뒤 반전시켜서 같은지 체크(팰린드롬)
    if arr == arr[::-1]:
        return True
    return False


for t in range(10):
    answer = 0
    n = int(input())
    maps = [list(input()) for _ in range(8)]

    # 행 체크
    for i in range(8):
        for j in range(8-n+1):
            row = []  # 행
            for k in range(n):
                row.append(maps[i][j+k])
            if check(row):
                answer += 1
    # 열 체크
    for i in range(8-n+1):
        for j in range(8):
            col = []  # 열
            for k in range(n):
                col.append(maps[i+k][j])
            if check(col):
                answer += 1

    print(f"#{t+1}", answer)