[4963번] 섬의 개수 - Python

문제

4963번: 섬의 개수

 

---

풀이

import sys
input = sys.stdin.readline
from collections import deque

# 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있음

dx = [-1, 0, -1, +1, +1, 0, +1, -1]
dy = [-1, -1, +1, 0, +1, +1, -1, 0]

def bfs(i, j):
    queue.append((i, j))
    visited[i][j] = 1

    while queue:
        x, y = queue.popleft()
        visited[x][y] = 1
        
        for k in range(8):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx >= 0 and nx < h and ny >= 0 and ny < w:
                if visited[nx][ny] != 1 and island_map[nx][ny] == 1:
                    visited[nx][ny] = 1
                    queue.append((nx, ny))
    

while True:
    # 너비, 높이
    w, h = map(int, input().split())

    if w == 0 and h == 0:
        break

    # 1은 땅, 0은 바다
    island_map = []


    visited = [[0] * w for _ in range(h)]
    island = 0

    for i in range(h):
        island_map.append(list(map(int, input().split())))

    queue = deque()
    for i in range(h):
        for j in range(w):
            if island_map[i][j] == 1 and visited[i][j] != 1:
                bfs(i, j)
                island += 1
    print(island)

아이디어

• 핵심은 상하좌우뿐 아니라 대각선으로도 탐색한다.
• x, y 개념은 (x, y)로 사용하였고 x에 들어가는 수는 0 ~ h-1 범위, y에 들어가는 수는 0 ~ w-1 범위이다.

 

시간 복잡도

O(노드의 개수 + 간선의 개수) => O(노드의 개수) => O(w*h)

 

공간 복잡도

O(w*h)