개요

문제링크

처음에 보고 조금 당황했던 문제
그냥 단순하게 생각하고 접근하면 풀리는 쉬운 문제였다.

문제분석

길이가 주어지면 해당 길이에 맞는 빈칸(연속된 빈칸을 하나의 빈칸이라고 하자)을 구하면 되는 문제이다.

낱말풀이를 할 때 흔히 볼 수 있는 그림이다.

위의 그림을 보면, 왼쪽에서 오른쪽으로 가는 칸과 위에서 아래로 내려가는 칸 두가지 경우가 있다.

우리는 두가지 경우를 모두 체크해주면 된다.

첫번째로, 왼쪽에서 오른쪽으로 가는 칸이다. 그냥 2차원 배열을 돌다가 달어가 들어가는 흰공간이 나오면,오른쪽으로 가다가 검은칸 혹은 경계선이 나오게 되면 멈추면 된다. 이때 핵심 포인트는 visited 배열을 통해 이미 오른쪽으로 한번 갔으면 visited 배열에 표현해주어야 한다.

방문배열 없이 하게 된다면, 왼쪽 맨 끝이 아닌 경우에도 체크하는 불상사가 발생한다.

두번째로 위에서 아래로가는 경우이다. 이 경우도 비슷하게 구할 수 있다. 이차원 배열을 탐색하다가. 아래로 내려갈 수 있다면. 검은칸 혹은 경계선을 만나기 전까지 길이를 체크해주면 된다.

이 문제를 통한 교훈은 무조건 bfs,dfs를 생각하지말고 단순하게 생각해보라는 것이었다. 보자마자 이걸 dfs!! 하면서 달려들려고 했지만. 찬찬히 다시 생각해보니 더 단순하게 풀 수 있는 방법이 있었다.

문제풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * @author onyoo
 * @performance
 * @category
 * @note
 * @see
 * @since 11/27/23
 **/
public class Solution {
	static int T,N,K,answer;
	static int[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		T = Integer.parseInt(br.readLine());
		for(int t=1;t<T+1;t++){
			st = new StringTokenizer(br.readLine()," ");
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			answer = 0;
			map = new int[N][N];

			for(int i=0;i<N;i++){
				st = new StringTokenizer(br.readLine()," ");
				for(int j=0;j<N;j++){
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			// 단어가 들어갈 수 없는 공간은 0, 들어갈 수 있는 공간은 1
			boolean[][] visited_row = new boolean[N][N];
			boolean[][] visited_col = new boolean[N][N];
			for(int i=0;i<N;i++){
				for(int j=0;j<N;j++){
					if(map[i][j] == 1 && !visited_row[i][j]){
						int nx = i;
						int ny = j;

						int row = 1;
						visited_row[nx][ny] = true;

						while(true){
							ny+=1;
							if(ny >= N) break;
							if(map[nx][ny] == 0) break;
							if(visited_row[nx][ny]) break;
							visited_row[nx][ny] = true;
							row++;
						}
						if(row == K) answer++;
					}

				} // 오른쪽으로 가면서 탐색
				for(int j=0;j<N;j++){
					if(map[i][j] == 1 && !visited_col[i][j]){
						int nx = i;
						int ny = j;

						int col = 1;
						visited_col[nx][ny] = true;
						while(true){
							nx+=1;
							if(nx >= N) break;
							if(map[nx][ny] == 0) break;
							visited_col[nx][ny] = true;
							col++;
						}
						if(col == K) answer++;
					}
				}
                //위에서 아래로 가면서 탐색
			}
			System.out.printf("#%d %d\n",t,answer);
		}
	}


}