[D2] 1979. 어디에 단어가 들어갈 수 있을까

1979. 어디에 단어가 들어갈 수 있을까

 

✏️ 문제 풀이

- 가로와 세로 모두 빈 공간(1)의 연속된 개수를 세어, K와 일치하는 경우를 카운트

 

- 가로 방향 (puzzle은 2차원 리스트로, 각 행(row)을 순회)
→ 현재 셀의 값이 1인 경우,  consecutive를 1 증가시킴.
→ 현재 셀의 값이 0인 경우, 즉 막힌 공간인 경우 
지금까지 세어진 1의 개수가 K와 같다면, K 길이의 단어가 들어갈 수 있는 자리이므로 count 1 증가
막힌 공간을 만나면 연속 카운트를 초기화
→ 행의 마지막 셀을 체크하고, 만약 마지막 셀까지 1이 연속으로 K개였다면 이를 카운트에 포함시킴

 

- 세로 방향 (열(column)을 순회하기 위해 0부터 n-1까지의 인덱스를 사용)

def count_valid(puzzle, n, k):
    count = 0
    
    # 가로 방향 확인
    for row in puzzle:
        consecutive = 0
        for cell in row:
            if cell == 1:
                consecutive += 1
            else:
                if consecutive == k:
                    count += 1
                consecutive = 0
        if consecutive == k:  # 마지막에 k가 될 수 있음
            count += 1
            
    # 세로 방향 확인
    for col in range(n):
        consecutive = 0
        for row in range(n):
            if puzzle[row][col] == 1:
                consecutive += 1
            else:
                if consecutive == k:
                    count += 1
                consecutive = 0
        if consecutive == k:  # 마지막에 k가 될 수 있음
            count += 1
            
    return count  

T = int(input())

for tc in range(1, T + 1):
    n, k = map(int, input().split())
    puzzle = [list(map(int, input().split())) for _ in range(n)]
    
    result = count_valid(puzzle, n, k)
    
    print(f"#{tc} {result}")