419. Battleships in a Board (Array, Depth-First Search, Matrix)

링크 - https://leetcode.com/problems/battleships-in-a-board/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

DFS로 풀 수 있는 문제이다. 또한 Top-Left X cell만 구하는 식으로도 풀 수 있다.

Code

# DFS
class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        ans = 0

        rows = len(board)
        cols = len(board[0])

        for row in range(rows):
            for col in range(cols):
                if board[row][col] == "X":
                    ans += 1
                    board[row][col] = "O"

                    queue = []
                    queue.append((row, col))
                    while queue:
                        r, c = queue.pop()
                        # Vertical spaceship
                        if (r > 0 and board[r-1][c] == "X") or (r < rows-1 and board[r+1][c] == "X"):
                            if r > 0 and board[r-1][c] == "X":
                                queue.append((r-1, c))
                                board[r-1][c] = "O"
                            if r < rows-1 and board[r+1][c] == "X":
                                queue.append((r+1, c))
                                board[r+1][c] = "O"
                        # Horizontal spaceship
                        elif (c > 0 and board[r][c-1] == "X") or (c < cols-1 and board[r][c+1] == "X"):
                            if c > 0 and board[r][c-1] == "X":
                                queue.append((r, c-1))
                                board[r-1][c] = "O"
                            if c < cols-1 and board[r][c+1] == "X":
                                queue.append((r, c+1))
                                board[r][c+1] = "O"

        return ans

# Top-Left cell counts
class Solution(object):
    def countBattleships(self, board):
        return sum(
            board[i][j] == 'X' and 
            (i == 0 or board[i - 1][j] == '.') and 
            (j == 0 or board[i][j - 1] == '.')
            for i in range(len(board))
            for j in range(len(board[0]))
        )

Complexity

Time Complexity: O(m*n)

Space Complexity: O(1)