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

[문제]

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

문제 풀기

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

 

---

[풀이]

• N x N 크기의 퍼즐을 중심으로 테두리 부분에 한칸씩 더 만든다
• 행과 열을 각각 확인하는 과정에서, 값이 0이고 다음 부분의 값이 1이면 cnt 값을 증가시킨다.
• 값이 1일때 다음부분의 값이 1이면 cnt 값을 증가시키고, 0이면 cnt 값이 k와 같은지 확인한다.
• cnt와 k 값이 같다면 result 값을 증가 시키고 다르다면 cnt를 0으로 초기화 한다.

import java.util.Scanner;

class Solution {
	public static void main(String[] args) throws Exception {		
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		for(int tc=1; tc<=t; tc++) {
			int n = sc.nextInt();
			int k = sc.nextInt();
			
			int map[][] = new int[n+2][n+2];
			
			int result = 0;
			
			for(int i=1; i<=n; i++) {				
				for(int j=1; j<=n; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			
			for(int i=0; i<n+2; i++) {
				int cnt = 0;
				
				for(int j=0; j<n+1; j++) {
					if(map[i][j] == 0) {
						if(map[i][j+1] == 1) cnt++;
					}
					else {
						if(map[i][j+1] == 1) cnt++;
						else {
							if(cnt == k) result++;
							cnt = 0;
						}
					}
				}
				if(cnt == k) result++;
			}			
			
			for(int i=0; i<n+2; i++) {
				int cnt = 0;
				
				for(int j=0; j<n+1; j++) {
					if(map[j][i] == 0) {
						if(map[j+1][i] == 1) cnt++;
					}
					else {
						if(map[j+1][i] == 1) cnt++;
						else {
							if(cnt == k) result++;
							cnt = 0;
						}
					}
				}
				if(cnt == k) result++;
			}	
			System.out.format("#%d %d\n", tc, result);
		}
	}
}