나의 논리
논리적으론 맞는것 같은데..시간초과가 나서 계속 틀렸다.
비슷한 문제를 백준에서 본적 이있는데, 아파트였나? 선거구였나? 이런걸 구하는 문제였다. 리트코드문제는 좀 더 쉬운것 같지만 접근하는 방법은 쉬운것 같다.
2x2 형태의 맵을 다루는 문제다. 딱히 루트노트가 없고 (y,x)를 한 노드로 간주하고 하나의 노드에 여러 노드가 연결 될 수 있다는 점에서
이러한 문제는 보통 그래프 이론으로 접근을 하곤 했다.
그리고 맵에서 섬을 찾는문제다. 섬을 탐색한다라고 생각을 해도되며 그렇다면 그래프에서 탐색하는 문제이다. 따라서 BFS 또는 DFS를 이용한다. BFS는 보통 최단거리를 탐색하는데 쓰이므로, DFS를 이용하여 섬을 찾는게 어떨까? 생각을 했다.
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
n = len(grid[0])
discovered = []
dy = [1,-1,0,0]
dx = [0,0,1,-1]
def dfs(y,x):
discovered.append((y,x))
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if ny < 0 or ny >= m or nx <0 or nx >=n:
continue
if grid[ny][nx] == "1" and (ny,nx) not in discovered:
discovered.append((ny,nx))
dfs(ny,nx)
ret = 0
for y in range(len(grid)):
for x in range(len(grid[0])):
if grid[y][x] == "1" and (y,x) not in discovered:
ret += 1
dfs(y,x)
return ret일단 처음 제출한 시간초과 받은 코드이다. 메인 메서드의 2중 포문에서 반복을 시작할때 한 좌표가 1이라서 섬이면 거길 시작으로 깊이 우선 탐색을 통해 연결된 육지를 모두 연결한다는 생각으로 discovered 리스트에 넣는다. 그럼 연결된 육지는 다음번에는 탐색을 안한다. 이렇게 dfs가 1번 끝나면 하나의 큰 육지는 찾은것이므로 육지의 갯수를 업데이트를 하고 다음 좌표로 넘어간다.
근데 일단..시간초과가 난다. C++로 했으면 통과했지 않을까 싶다.
정답 논리
시간초과로 이리저리 고민을 하다가 '파이썬 알고리즘 인터뷰'책의 해답을 보게됬다. 책의 코드를 싣기에는 조금 조심스럽지만..
discovered 리스트에 저장하는대신 맵을 0으로 만들어 다음에 탐색이 안되도록 만들었다. 아마 not in 연산이 조금 부하를 줬을꺼라고 생각한다.
