SWEA 1979번: 어디에 단어가 들어갈 수 있을까 (D2) - Python 풀이

ㅋㅋ 저도 묻고 싶습니다.
어디(회사)에 제가 들어갈 수 있을까요

문제 설명

SW Expert Academy

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부터 시작한다.)

입력

10

5 3

0 0 1 1 1

1 1 1 1 0

0 0 1 0 0

0 1 1 1 1

1 1 1 0 1

5 3

1 0 0 1 0

1 1 0 1 1

1 0 1 1 1

0 1 1 0 1

0 1 1 1 0

…

input.txt

출력

#1 2

#2 6

...

output.txt

풀이 과정

N*N에서 연속으로 1이 나오는 것이 딱 K칸이 있을 때 카운트를 증가합니다.

경우는 2가지가 됩니다. 1) 가로로 1이 K칸 연속 2) 세로로 1이 K칸 연속

그래서 1) 가로를 쭉 보면서 찾고 2) 세로로 쭉 보면서 찾으면 되겠다고 생각했습니다.

예제처럼 N=5, K=3일 때 가로로 1이 연속 3개가 되는 경우는 11100 / 01110 / 00111 / 10111 / 11101 가 있습니다. 이렇게 연속으로 딱 3개만 있으려면 111의 양옆이 0이거나 111이 맨 끝에 있어야 합니다.

01011 같은 경우는 1이 3개이긴 하지만 연속하지 못하고 중간에 0이 끼어있기 때문에 해당하지 않습니다. 그렇기 때문에 1의 개수만 무작정 찾는 것이 아니라, 0이 나올 때에는 카운트를 초기화 해주는 방식으로 구현해야 합니다.

정답 코드

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N, K = map(int, input().split())
    arr = [[] for _ in range(N)]

    for i in range(N):
        arr[i] = list(map(int, input().split()))

    answer = 0

    # 가로로 K칸 연속 1인 거 찾기
    for i in range(N):
        cnt = 0
        for j in range(N):
            if arr[i][j] == 1:
                cnt += 1
            else:
                if cnt == K:
                    answer += 1
                cnt = 0
        if cnt == K:
            answer += 1

    # 세로로 K칸 연속 1인 거 찾기
    for i in range(N):
        cnt = 0
        for j in range(N):
            if arr[j][i] == 1:
                cnt += 1
            else:
                if cnt == K:
                    answer += 1
                cnt = 0
        if cnt == K:
            answer += 1

    print("#%d" % test_case, answer)

이상입니다.