num of Islands를 복습하면서 궁금한 것이 있습니다.

먼저 제가 짠 시간초과 난 소스코드는 다음과 같습니다

from collections import deque

class Solution(object):
    def numIslands(self, grid):
        m = len(grid)  # row
        n = len(grid[0])  # col
        visited = []
        ans = [[False] * n for _ in range(m)] # ans의 용도가 뭐지?
        cnt = 0

        def bfs(x, y):
            q = deque()
            # 사전 세팅
            q.append((x, y))
            visited.append((x,y))
            dx = [-1, 1, 0, 0]
            dy = [0, 0, -1, 1]

            while q:
                cur_x, cur_y = q.popleft()  # (0,0)
                
                for i in range(4):
                    next_x = cur_x + dx[i]
                    next_y = cur_y + dy[i]

                    if next_x >= 0 and next_x < m and next_y >= 0 and next_y < n:
                        if grid[next_x][next_y] == "1" and (next_x, next_y) not in visited:
                            q.append((next_x, next_y))
                            visited.append((next_x, next_y))
                            ans[next_x][next_y] = True
        
        # 완전탐색
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1" and (i, j) not in visited:
                    bfs(i, j)
                    cnt += 1
        return cnt

grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"],
]

sol = Solution()
print(sol.numIslands(grid))  # O/P: 3

발상은 비슷한 것 같은데, 기억에서는 ans를 저렇게 작성한 것 같아서 위와 같이 초기화를 했지만 ans의 용도를 몰랐고 bfs 템플릿을 참고해서 visited.append()로 방문한 정점을 추가했습니다. 그런데 이렇게하면 테스트케이스 48/49에서 시간초과가 났습니다. 왜 그런지 알 수 있을까요?

if grid[next_x][next_y] == "1" and (next_x, next_y) not in visited: