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

어디에 단어가 들어갈 수 있을까 URL

내 풀이

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

public class SW1979 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            int[][] graph = new int[N][N];

            //graph 채우기
            for (int i = 0; i < N; i++) {
                StringTokenizer st2 = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    graph[i][j] = Integer.parseInt(st2.nextToken());

                }
            }
            

            int answer = 0;
            for (int x = 0; x < N; x++) {
                int w_cnt = 0; int h_cnt = 0;
                for (int y = 0; y < N; y++) {
                    //가로
                    if (graph[x][y] == 1) {
                        w_cnt++;
                    } else {
                        w_cnt = 0;
                    }
                    
                    if (w_cnt == K && y != N-1 && graph[x][y+1] == 0) {
                        answer++;
                    } else if (w_cnt == K && y == N-1) {
                        answer++;
                    }
                    
                    //세로
                    if (graph[y][x] == 1) {
                        h_cnt++;
                    } else {
                        h_cnt = 0;
                    }

                    if (h_cnt == K && y != N-1 && graph[y+1][x] != 1) {
                        answer++;
                    } else if (h_cnt == K && y == N-1) {
                        answer++;
                    }

                }    
            }

            System.out.println("#" + t + " " + answer);
        }
    }
}

배운점

처음에 행렬 그래프를 보고 DFS탐색으로 푸는건가 싶어서 DFS함수를 만들었는데
문제를 다시 읽어보니 가로줄 따로 세로줄 따로 확인해야되는 구현문제인 것을 알게되었다.

풀이

1. 먼저 graph를 입력받아서 채운다.
2. 모든 행렬을 돌면서 확인하기 위해 2중 for문을 사용한다.
3. 가로 따로 세로 따로 돌면서 1의 숫자를 세기 위해 각각의 cnt를 생성한다.
4. 가로 한줄 세로 한줄 돌면서 1이면 더해주고 아니면 cnt를 0으로 초기화

• 조건1: 만약 K와 cnt가 같을 때 다음 칸이 있을경우 0이면 answer++
• 조건2: 만약 K와 cnt가 같을 때 다음은 벽인 경우 answer++

처음엔 가로 세로를 따로 계산해준 뒤 각각의 수를 더해주는 방식으로 풀었는데
굳이 이중for문을 두개 만들필요 없이 하나로 합칠 수 있다고 판단하여 하나로 합쳤습니다.
그 결과 실행 속도와 메모리 사용량의 효율성이 크게 증가되었습니다.