문제 출처 : [SWEA] 1979 어디에 단어가 들어갈 수 있을까

문제

N X N 크기의 단어 퍼즐을 만들려고 한다. 입력으로 단어 퍼즐의 모양이 주어진다.

주어진 퍼즐 모양에서 특정 길이 K를 갖는 단어가 들어갈 수 있는 자리의 수를 출력하는 프로그램을 작성하라.

N = 5, K = 3 이고, 퍼즐의 모양이 아래 그림과 같이 주어졌을 때

길이가 3 인 단어가 들어갈 수 있는 자리는 2 곳(가로 1번, 가로 4번)이 된다.

제약 사항

1. N은 5 이상 15 이하의 정수이다. (5 ≤ N ≤ 15)

2. K는 2 이상 N 이하의 정수이다. (2 ≤ K ≤ N)

입력

입력은 첫 줄에 총 테스트 케이스의 개수 T가 온다.

다음 줄부터 각 테스트 케이스가 주어진다.

테스트 케이스의 첫 번째 줄에는 단어 퍼즐의 가로, 세로 길이 N 과, 단어의 길이 K 가 주어진다.

테스트 케이스의 두 번째 줄부터 퍼즐의 모양이 2차원 정보로 주어진다.

퍼즐의 각 셀 중, 흰색 부분은 1, 검은색 부분은 0 으로 주어진다.

출력

테스트 케이스 t에 대한 결과는 “#t”을 찍고, 한 칸 띄고, 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

코드

import sys
sys.stdin = open('1979_word_puzzle.txt')

T = int(input())
for tc in range(1, T + 1):
    # N : 배열의 크기, K : 문자열의 길이
    N, K = map(int, input().split())
    # 주어진 배열을 받아오면서 상하좌우 1칸씩 0으로 추가
    puzzle = [[0] * (N + 2)] + [[0] + list(map(int, input().split())) + [0] for _ in range(N)] + [[0] * (N + 2)]
    result = 0      # 최종 결과값을 반환할 변수 초기화

    # 양쪽 여백을 제외하기 위해 1 ~ N + 1까지 반복
    for i in range(1, N + 1):
        # 길이가 K만큼의 문자열을 앞에서부터 비교하며 한칸씩 전진하기 위한 반복문
        for j in range(1, N - K + 2):
            cnt_row = 0     # 가로줄에서 K번 연속된 1의 개수를 저장할 변수 초기화
            cnt_col = 0     # 세로줄에서 K번 연속된 1의 개수를 저장할 변수 초기화
            # 가로줄에서 K의 양 옆의 숫자가 0인 경우를 찾음
            if puzzle[i][j - 1] == 0 and puzzle[i][K + j] == 0:
                # K 구간 내에 1이 몇 개 존재하는지 탐색
                for n in range(K):
                    # 1이 있다면 cnt_row + 1
                    if puzzle[i][j + n]:
                        cnt_row += 1
            # 세로줄에서 K의 위, 아래의 숫자가 0인 경우를 찾음
            if puzzle[j - 1][i] == 0 and puzzle[K + j][i] == 0:
                # K 구간 내에 1이 몇 개 존재하는지 탐색
                for n in range(K):
                    # 1이 있다면 cnt_row + 1
                    if puzzle[j + n][i] == 1:
                        cnt_col += 1
            # 구간 탐색 후 가로줄과 세로줄에 1이 K번 연속되었을 때 result + 1
            if cnt_row == K:
                result += 1
            if cnt_col == K:
                result += 1

    print('#{} {}'.format(tc, result))

풀이 방법

1이 K번 연속된 경우가 몇 번 나타나는지를 찾는 문제이다. 예를 들어 K가 3인 경우 1이 4번 연속되는 구간은 카운트하지 않는다.

그래서 처음 단어 퍼즐을 인풋 받을 때 사방을 0으로 둘러서 받았다. 1이 K번 연속되었다는 말은 1로 연속된 구간의 양쪽 끝에 0이 있다는 뜻이기 때문이다.
하지만 지금 다시 보니 4방향을 다 막아줄 필요는 없고 세로줄 판별을 위해 위쪽에 한 줄, 가로줄 판별을 위해 오른쪽에 한 줄만 추가했어도 됐을 것 같다.