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

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PuPq6AaQDFAUq&categoryId=AV5PuPq6AaQDFAUq&categoryType=CODE

SW Expert Academy

시뮬레이션 문제. D2 치고는 조금 생각해야 하는 문제였다. (앞에서 푼 시각 덧셈이랑 난이도 차이가 꽤 있다.)

 

풀이

1. 입력을 모두 받은 후에 값이 1인 곳에 대해서만 모두 검색을 해준다.
2. 가로를 검사하는 경우와 세로를 검사하는 경우를 나누어 주었다.
   1. 세로를 검사하는 경우
      • 시작칸이 첫 번째 칸이거나 바로 앞의 칸 값이 0이어야 한다.
      • 현재 칸을 포함해서 아래로 K칸만큼이 범위를 벗어나면 안 된다.
      • 위의 조건을 만족한다면 현재 칸을 포함한 K칸만큼 동안 하나라도 0을 가지면 false
      • 현재 칸을 포함한 K칸 이후의 바로 다음 칸이 범위를 벗어나지 않는다면 0 값을 가지는지 확인해준다. (1 값을 가지면 false)
   2. 가로를 검사하는 경우도 똑같은 방식으로 j열에 대해서 검사해주면 된다.
3. check함수를 통해 true 값을 count 값을 증가시킨다.

 

import java.io.*;
import java.util.StringTokenizer;

public class Solution {

	static int N,K;
	static int[][] puzzle;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			puzzle = new int[N][N];
			
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					puzzle[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			int count = 0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(puzzle[i][j] == 0) continue; //단어가 들어갈수 없는 칸
					
					if(i == 0 || puzzle[i-1][j] == 0) { //첫번째 칸이거나 바로 앞에 칸이 0
						if(i+K <= N) { //범위를 넘어가지 않는 경우에만 검사
							if(checkSero(i,j)) {
								count += 1;
							}
						}
					}
					
					
					if(j == 0 || puzzle[i][j-1] == 0) { //첫번째 칸이거나 바로 앞에 칸이 0
						if(j+K <= N) { //범위를 넘어가지 않는 경우에만 검사
							if(checkGaro(i,j)) {
								count += 1;
							}
						}
					}
				}
			}
			
			System.out.println("#"+tc+" "+count);
			
		}
	}
	
	static boolean checkSero(int x, int y) {
		boolean flag = true;
		int n = x+K;
		for(int i=x; i<n; i++) {
			if(puzzle[i][y] == 0) {
				flag = false; //하나라도 0값이 있으면 false (단어를 넣을 수 없으면)
				break;
			}
		}
		if(x+K < N) {
			if(puzzle[x+K][y] == 1)
				flag = false; //넣을 단어보다 칸이 길면 false
		}
		
		return flag;
	}
	
	static boolean checkGaro(int x, int y) {
		boolean flag = true;
		int n = y+K;
		for(int j=y; j<n; j++) {
			if(puzzle[x][j] == 0) {
				flag = false; //하나라도 0값이 있으면 false (단어를 넣을 수 없으면)
				break;
			}
		}
		if(y+K < N) {
			if(puzzle[x][y+K] == 1)
				flag = false; //넣을 단어보다 칸이 길면 false
		}
		
		return flag;
	}

}