SWEA - 어디에 단어가 들어갈 수 있을까(1979)

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)

 

 

접근방식

0과 1로 이뤄진 NxN 배열이 주어지면 연속된 행과 열에서 1의 값이 K의 길이만큼 있는 것들의 개수를 세는 문제

행과 열로 나눠서 값을 구하고 더해주는 문제

먼저 N만큼 for문을 2번 돌면서 arr[k][x]가 1이면 cnt 변수에 1을 더해줌

그리고 arr[k][x]가 0이거나 x == N-1(마지막 인수)이면 먼저 cnt와 K가 같은지 체크

같으면 result += 1을 해줌. 그리고 arr[k][x] == 0이면 cnt = 0으로 초기화

같은 작업을 열에도 적용

 

if arr[k][x] == 0 or x == N-1:
    if cnt == K:
    	result += 1
    if arr[k][x] == 0:
    	cnt = 0

이부분에서 cnt == K를 arr[k][x] == 0보다 먼저 해주는 이유:

예로 arr[1][0]~ arr[1][4] 가 [1, 1, 1, 0, 0]일 경우 앞선 조건문에 의해 cnt = 3이 되어있을 것임

여기서 arr[1][3] == 0 or 3 == N-1 이 조건문 중 arr[1][3] == 0에 의해 위 조건문에 해당되므로 if문을 돌텐데

만약 arr[k][x] == 0 조건문이 cnt == K 조건문보다 위에 있으면 arr[1][3] == 0이므로 cnt = 0이 됨

그 후 cnt == K 조건문에서 0 == 3이므로 result += 1라는 수식을 할 수가 없음

 

 

코드

T = int(input())
for i in range(1, T+1):
    N, K = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]
    
    result = 0
    for k in range(N):
        cnt = 0
        for x in range(N):
            if arr[k][x] == 1:
                cnt += 1
            if arr[k][x] == 0 or x == N-1:
                if cnt == K:
                    result += 1
                if arr[k][x] == 0:
                    cnt = 0
    
    for a in range(N):
        cnt = 0
        for b in range(N):
            if arr[b][a] == 1:
                cnt += 1
            if arr[b][a] == 0 or b == N-1:
                if cnt == K:
                    result += 1
                if arr[b][a] == 0:
                    cnt = 0
    print('#'+str(i), result)