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

코딩테스트 [ ALL IN ONE ]

[코테 적용] 👉 [1번 문제] 완전 탐색 (후반부)

해결된 질문

작성

177

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

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에서 시간초과가 났습니다. 왜 그런지 알 수 있을까요?

python 코딩-테스트 알고리즘

답변 1

개발남노씨

지식공유자

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

여기서 (next_x, next_y) not in visited 를 해버리면 visited리스트를 모두 다 탐색해서 (next_x, next_y)이 있는지 없는지를 살펴봐야해요 - O(n)
그래서 visited를 set으로 선언하든지, 이차원배열로 선언해서 visited[next_x][next_y] 좌표가 True인지 False인지 확인하는 코드로 변경하면 O(1)으로 짤 수 있어요!!

한번 해당내용 참고해서 고민 더 해보시면 도움 많이 될거에요 ㅎㅎ

Ambition

질문자

아! in 연산자가 딕셔너리(HashMap), HashSet, 그리고 리스트 이렇게가 있었군요 이 중에 리스트 제외한 것들은 O(1)의 시간복잡도만 걸리구요 감사합니다

그러면 set(visited)로 선언하면 굳이 visited = [[False] * n for _ in range(m)]과 같이 초기화할 필요가 없나요?

-> 빈 리스트로 선언한 visited를 모두 해시셋으로 바꾸니 정상적으로 테케 통과하네요 감사합니다 :)

인프런 커뮤니티 질문&답변

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