[SWEA] 1979 : 어디에 단어가 들어갈 수 있을까 (Python/파이썬)

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5PuPq6AaQDFAUq&categoryId=AV5PuPq6AaQDFAUq&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1

문제

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

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

[제약 사항]

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
…

출력

#1 2
#2 6
...

---

정답 및 풀이

t = int(input())

for tc in range(1, t+1):
    n, k = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    result = 0

    for i in range(n):
        cnt = 0
        for j in range(n):
            if arr[i][j] == 1:
                cnt += 1
            if arr[i][j] == 0 or j == n-1:
                if cnt == k:
                    result += 1
                cnt = 0

    for j in range(n):
        cnt = 0
        for i in range(n):
            if arr[i][j] == 1:
                cnt += 1
            if arr[i][j] == 0 or i == n-1:
                if cnt == k:
                    result += 1
                cnt = 0

    print(f'#{tc} {result}')

1. t = int(input())
   • 테스트 케이스 개수를 입력받는다.
2. n, k = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(n)] result = 0
   • n: 퍼즐의 크기
   • k: 단어의 길이
   • arr: 퍼즐을 저장한 2차원 리스트
   • result: 단어가 들어갈 수 있는 위치의 개수를 저장한다.
3. for i in range(n): cnt = 0 for j in range(n):
   • 가로 방향 검사를 위해 행 i를 고정한다.
   • cnt는 연속된 1의 개수를 세는 변수다.
4. if arr[i][j] == 1: cnt += 1
   • 현재 칸이 1이면 연속 구간이 이어지고 cnt를 1 증가시킨다.
5. if arr[i][j] == 0 or j == n-1: if cnt == k: result += 1 cnt = 0
   • 현재 칸이 0이거나 마지막 칸이면 ‘연속된 1 구간’이 끝난 것이다.
   • 구간의 길이가 k와 정확히 같다면 result를 1 증가시킨다.
   • 그 후 cnt를 0으로 초기화해 다음 구간을 준비한다.
6. for j in range(n): cnt = 0 for i in range(n):
   • 이번에는 세로 방향을 검사한다.
   • j는 열 고정, i는 행 인덱스 역할을 한다.
7. if arr[i][j] == 1: cnt += 1
   • 세로 방향에서도 연속된 1이면 cnt를 증가시킨다.
8. if arr[i][j] == 0 or i == n-1: if cnt == k: result += 1 cnt = 0
   • 세로 방향에서도 0을 만나거나 마지막 줄에 도착하면 연속 구간이 끝난 것이다.
   • cnt가 k와 같다면 result를 증가시킨다.
   • cnt는 다시 0으로 초기화한다.
9. print(f'#{tc} {result}')
   • 테스트 케이스 번호와 단어가 들어갈 수 있는 총 개수를 출력한다.

---