[백준|파이썬] 4963: 섬의 개수 (실버2)

문제

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

4963번: 섬의 개수

 

 

🐍파이썬

import sys
from collections import deque

#상하좌우, 대각선 모두 방문하기 위해 좌표설정
dy = [-1, 1, 0, 0, -1, 1, -1, 1]
dx = [0, 0, -1, 1, 1, 1, -1, -1]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= h or ny >= w or nx < 0 or ny < 0:	#배열의 범위를 넘어서는 경우 건너뛰기
                continue
            if island[nx][ny] == 0:	#바다인 경우 건너뛰기
                continue
            if island[nx][ny] == 1:	#육지인 경우
                island[nx][ny] = 0	#중복 피하기 위해 0으로 덮어씌워 방문처리
                queue.append((nx, ny))	#다음 육지를 찾기 위해 큐에 현재의 좌표 저장

while True:
    w, h = map(int, sys.stdin.readline().split())
    if w == 0 and h == 0:
        break
    island = []
    for i in range(h):
        island.append(list(map(int, sys.stdin.readline().split())))
    visited = [[0] * w for _ in range(h)]
    answer = 0
    for i in range(h):
        for j in range(w):
            if island[i][j] == 1:	#육지인 경우
                bfs(i, j)	#bfs를 이용해 연결된 모든 육지를 발견
                answer += 1	#이어진 육지를 하나씩 발견할 때마다 answer+1
    print(answer)