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

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

SW Expert Academy

 

문제

 

입력

 

출력

 

---

소스코드

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

class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            int arr[][] = new int[n][n];
            for (int j = 0; j < n; j++) {
                st = new StringTokenizer(br.readLine());
                for (int l = 0; l < n; l++) {
                    arr[j][l] = Integer.parseInt(st.nextToken());
                }
            }

            int result = 0;
            for (int j = 0; j < n; j++) {
                for (int l = 0; l < n; l++) {
                    if (arr[j][l] == 0) continue;
                    // 위가 막혀있을 때
                    if (j - 1 < 0 || arr[j - 1][l] == 0) {
                        int count = 0;
                        for (int m = j; m < n; m++) {
                            if (arr[m][l] == 1) count++;
                            else break;
                        }
                        if (count == k) result++;
                    }
                    // 왼쪽이 막혀있을 때
                    if (l - 1 < 0 || arr[j][l - 1] == 0) {
                        int count = 0;
                        for (int m = l; m < n; m++) {
                            if (arr[j][m] == 1) count++;
                            else break;
                        }
                        if (count == k) result++;
                    }
                }
            }

            sb.append("#" + (i + 1) + " " + result + "\n");
        }
        System.out.println(sb);
    }
}

 

해결 방법

1. 해당 칸은 막혀있지 않으면서, 해당 칸의 상단 또는 좌측이 막혀있어야 단어가 들어갈 수 있는지 확인할 수 있다.
2. 해당 칸은 막혀있지 않고, 해당 칸의 상단이 막혀있다면 하단을 탐색하여 단어가 딱 맞게 들어가는 지 확인한다.
3. 해당 칸은 막혀있지 않고, 해당 칸의 좌측이 막혀있다면 우측을 탐색하여 단어가 딱 맞게 들어가는 지 확인한다.
4. 딱 맞게 들어간다면 result를 증가시킨다.