C++로 2D 보드에서 전함 개수 세는 방법

문제 소개

2차원 보드가 주어졌을 때, 보드 위에 있는 전함(battleship)의 개수를 세는 문제입니다. 전함은 문자 'X'로 표현되며, 빈 칸은 '.'으로 표현됩니다. 이때 다음과 같은 규칙이 성립한다고 가정할 수 있습니다.

주어지는 보드는 항상 유효하며, 전함 또는 빈 칸으로만 구성되어 있습니다.
전함은 가로 또는 세로 방향으로만 배치할 수 있습니다. 즉, 전함의 형태는 1xN(1행 N열) 또는 Nx1(N행 1열)이며, N은 어떤 크기든 가능합니다.
두 전함 사이에는 최소 하나의 가로 또는 세로 빈 칸이 존재합니다. 즉, 서로 인접한 전함은 없습니다.

예를 들어 보드가 다음과 같다면:

X	.	.	X
.	.	.	X
.	.	.	X

전함이 두 척 존재하므로 출력값은 2가 됩니다.

접근 방법

이 문제는 각 칸을 한 번씩만 확인하면 되므로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 전함의 시작 지점(가장 왼쪽 위 칸)만 카운트하는 것입니다. 어떤 'X' 칸의 위쪽과 왼쪽이 모두 'X'가 아니라면, 그 칸은 새로운 전함의 시작점이 됩니다.

해결 단계는 다음과 같습니다.

ans := 0으로 초기화하고, n := 행의 개수, m := 열의 개수로 설정합니다.
i번째 행에 대해:
- j번째 열에 대해:
  - board[i][j]가 '.'이라면 다음 반복으로 넘어갑니다.
  - i > 0이고 board[i-1][j] == 'X'라면 다음 반복으로 넘어갑니다. (위쪽에 이미 전함이 있으므로 현재 칸은 같은 전함의 일부입니다.)
  - j > 0이고 board[i][j-1] == 'X'라면 다음 반복으로 넘어갑니다. (왼쪽에 이미 전함이 있으므로 현재 칸은 같은 전함의 일부입니다.)
  - 위 조건에 해당하지 않으면 ans를 1 증가시킵니다.
모든 탐색이 끝나면 ans를 반환합니다.

이 방식은 보드 배열을 수정하지 않고도 추가 메모리 없이 전함의 개수를 정확하게 셀 수 있다는 장점이 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int countBattleships(vector<vector<char>>& board) {
        int ans = 0;
        int n = board.size();
        int m = board[0].size();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(board[i][j] == '.')continue;
                if(i > 0 && board[i - 1][j] == 'X')continue;
                if(j > 0 && board[i][j - 1] == 'X')continue;
                ans++;
            }
        }
        return ans;
    }
};
main(){
    vector<vector<char>> v = {{'X','.','.','X'},{'.','.','.','X'},{'.','.','.','X'}};
    Solution ob;
    cout << (ob.countBattleships(v));
}

입력

[["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]

출력

복잡도 분석

시간 복잡도: O(n × m) — 보드의 모든 칸을 정확히 한 번씩 확인합니다.
공간 복잡도: O(1) — 추가적인 자료구조 없이 상수 공간만 사용합니다.