백준 1652 누울 자리를 찾아라 JAVA 풀이 (구현, 문자열, 완전탐색, 시간복잡도)

🔗 문제 링크

https://www.acmicpc.net/problem/1652

---

📌 문제 개요

NxN 크기의 방이 주어지고, .은 빈칸, X는 벽을 의미한다.

가로 또는 세로로 연속된 빈칸이 2칸 이상이면 누울 수 있는 자리로 판단

- 가로 / 세로 각각 가능한 자리 개수를 구하는 문제

---

📌 접근 방법

이 문제는 단순 구현 문제로
연속된 '.'의 길이를 세는 방식으로 해결할 수 있다.

• 가로 방향 탐색
  • 한 행씩 보면서 '.' 개수 카운트
  • 'X'를 만나면 구간 종료
• 세로 방향 탐색
  • 동일한 방식으로 열 기준 탐색

---

📌 핵심 아이디어

• 연속된 '.' 구간을 찾는다
• 구간 길이가 2 이상이면 카운트
• 'X'를 기준으로 구간을 나눈다
• 가로와 세로는 완전히 별개로 계산

---

📌 전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        char[][] map = new char[N][N];

        for(int i = 0; i < N; i++){
            map[i] = br.readLine().toCharArray();
        }

        int rowCnt = 0;
        int colCnt = 0;

        // 가로
        for(int i = 0; i < N; i++){
            int cnt = 0;
            for(int j = 0; j < N; j++){
                if(map[i][j] == '.') cnt++;
                else {
                    if(cnt >= 2) rowCnt++;
                    cnt = 0;
                }
            }
            if(cnt >= 2) rowCnt++;
        }

        // 세로
        for(int j = 0; j < N; j++){
            int cnt = 0;
            for(int i = 0; i < N; i++){
                if(map[i][j] == '.') cnt++;
                else {
                    if(cnt >= 2) colCnt++;
                    cnt = 0;
                }
            }
            if(cnt >= 2) colCnt++;
        }

        System.out.println(rowCnt + " " + colCnt);
    }
}

---

🧾 정리

• 구현 난이도는 낮지만 구간 처리가 핵심
• 마지막 구간 체크를 빼먹기 쉬움 
• 가로/세로를 나눠서 생각하면 매우 쉬움