문제 상세 설명N X N 크기의 단어 퍼즐을 만들려고 한다. 입력으로 단어 퍼즐의 모양이 주어진다.
주어진 퍼즐 모양에서 특정 길이 K를 갖는 단어가 들어갈 수 있는 자리의 수를 출력하는 프로그램을 작성하라
N X N 크기의 단어 퍼즐을 만들려고 한다. 입력으로 단어 퍼즐의 모양이 주어진다.
주어진 퍼즐 모양에서 특정 길이 K를 갖는 단어가 들어갈 수 있는 자리의 수를 출력하는 프로그램을 작성하라.
[예제]
N = 5, K = 3 이고, 퍼즐의 모양이 아래 그림과 같이 주어졌을 때
길이가 3 인 단어가 들어갈 수 있는 자리는 2 곳(가로 1번, 가로 4번)이 된다.
[제약 사항]
-
N은 5 이상 15 이하의 정수이다. (5 ≤ N ≤ 15)
-
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 |
정답 코드
package D2;
import java.util.*;
public class N1979 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
StringBuilder result = new StringBuilder();
for (int i = 1; i <= T; i++) {
int N = scanner.nextInt();
int K = scanner.nextInt();
int[][] arr = new int[N][N];
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
arr[j][k] = scanner.nextInt();
}
}
result.append(String.format("#%d %d\n", i, solution(arr, N, K)));
}
System.out.print(result);
scanner.close();
}
public static int solution(int[][] arr, int N, int K) {
int count = 0;
// 가로 방향 탐색
for (int i = 0; i < N; i++) {
count += findSpaces(arr[i], K); // 행을 전달
}
// 세로 방향 탐색
for (int i = 0; i < N; i++) {
int[] column = new int[N];
for (int j = 0; j < N; j++) {
column[j] = arr[j][i];
}
count += findSpaces(column, K); // 열을 전달
}
return count;
}
// 특정 1차원 배열에서 K의 길이가 들어갈 공간 수 계산
public static int findSpaces(int[] line, int K) {
int count = 0;
int length = 0; // 연속된 1의 길이를 저장
for (int cell : line) {
if (cell == 1) {
length++; // 1이 연속되면 길이 증가
// 값이 0인 경우
} else {
if (length == K) count++; // 조건에 맞으면 카운트 증가
length = 0; // 초기
}
}
// 마지막에 끝나는 경우
if (length == K) count++;
return count;
}
}
접근 방법
- 탐색은 가로 방향 탐색, 세로 방향 탐색으로 진행한다.
- 각 행(열)을 순회하면서 연속된 1의 길이를 추적한다.
- 1의 길이가 K일때, 앞뒤가 0이거나 경계이면 카운트 증가한다.
- 0을 만나거나 경계를 넘어가면 길이를 초기화한다.
- 세로 탐색인 경우는 열 데이터를 별도의 배열로 추출해 진행한다.
