[백준알고리즘] 4963번: 섬의 개수 -Python

[백준알고리즘] 4963번: 섬의 개수 -Python

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

이전에 풀었던 단지번호붙이기 문제와 유사하다. 상하좌우의 값과 추가적으로 대각선만 더 고려해주면 된다.

 

마찬가지로 리스트를 스택으로 이용해서 DFS를 사용했고, 경곗값 검사는 스택에서 꺼낸 뒤에 해주었다. 미세하지만 아무래도 스택에 넣기 전에 si-1 > 0, sj-1 > 0, si+1 <= h, sj+1 <=w 처럼 무조건 두 번의 검사가 아닌 필요한 것만 해주는 것이 속도는 향상된다. 여기서는 미세하고 일일이 다 해주면 코드만 지저분해 보이기 때문에 빼주었다.

 

import sys

def dfs(i, j):
    global world

    stack = [(i, j)]
    while stack:
        si, sj = stack.pop()
        if not 0<si<=h or not 0<sj<=w or not world[si][sj]:
            continue
            
        world[si][sj] = 0
        stack.append((si-1, sj-1))
        stack.append((si-1, sj))
        stack.append((si-1, sj+1))
        stack.append((si, sj-1))
        stack.append((si, sj+1))
        stack.append((si+1, sj-1))
        stack.append((si+1, sj))
        stack.append((si+1, sj+1))

    return land

w, h = map(int, sys.stdin.readline().split())
while h + w != 0:
    world = [0]
    for _ in range(h):
        world.append([0] + list(map(int, sys.stdin.readline().split())))

    land = 0
    for i in range(1, h+1):
        for j in range(1, w+1):
            if world[i][j]:
                dfs(i, j)
                land += 1

    sys.stdout.write('{}\n'.format(land))
    w, h = map(int, sys.stdin.readline().split())

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다