Algorithm - 격자판 회문수

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[격자판 회문수]

 

1부터 9까지의 자연수로 채워진 7x7 격자판이 주어지면, 격자판 위에서 가로방향 또는 세로방향으로 길이 5자리 회문수가 몇 개 있는지 구하는 프로그램을 작성하시오. (회문수란 121과 같이 앞에서부터 읽으나 뒤에서부터 읽으나 같은 수를 의미함)

격자판

 

단, 빨간색처럼 구부러진 경우(87178)는 회문수로 간주하지 않는다.

 

 

*입력 설명

1부터 9까지의 자연수로 채워진 7x7 격자판이 주어진다.

 

*출력 설명

5자리 회문수의 개수를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_21.txt', 'rt')

board = [list(map(int, input().split())) for _ in range(7)]
cnt = 0

for i in range(3):
    for j in range(7):
        tmp = board[j][i:i+5]
        if tmp == tmp[::-1]:
            cnt += 1
        for k in range(2):
            if board[i + k][j] != board[i + 5 - k - 1][j]:
                break
        else:
            cnt += 1
print(cnt)

# 출력 : 3

 

input_21.txt(입력)

2 4 1 5 3 2 6 
3 5 1 8 7 1 7 
8 3 2 7 1 3 8 
6 1 2 3 2 1 1 
1 3 1 3 5 3 2  
1 1 2 5 6 5 2 
1 2 2 2 2 1 5

 

 

중요내용

1. tmp == tmp[::-1]은 행의 방향으로 회문을 검사하는 코드이다. (슬라이싱 기능 활용)
2. board[i + k][j] != board[i + 5 - k - 1][j]는 열의 방향으로 회문을 검사하는 코드이다.
3. 참고로, 열의 방향으로 회문을 검사하는 코드에서는 슬라이싱 기능을 활용하지 못하기 때문에 for문을 사용한다.