[백준 파이썬] 4963번 섬의 개수

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

4963번: 섬의 개수

 

<코드>

import sys
from collections import deque
input = sys.stdin.readline
dr = [0,1,0,-1,1,1,-1,-1]
dc = [1,0,-1,0,-1,1,1,-1]

def bfs(r, c):
    global cnt
    q = deque()
    q.append((r, c))
    while q:
        r, c = q.popleft()
        for d in range(8):
            nr = r + dr[d]
            nc = c + dc[d]
            if 0 <= nr < h and 0 <= nc < w and arr[nr][nc] == 1:
                arr[nr][nc] = 0
                q.append((nr, nc))


while True:
    w, h = map(int, input().split())
    if w == h == 0:
        break
    cnt = 0
    arr = [list(map(int, input().split())) for _ in range(h)]


    for i in range(h):
        for j in range(w):
            if arr[i][j] == 1:
                bfs(i, j)
                cnt += 1
    print(cnt)

 

<풀이방법>

8방향으로 bfs탐색

땅인 경우에 그 지점부터 연결된 땅 다 0으로 바꿔주고 cnt +=1

그 다음 땅인 경우 찾아서 반복

cnt 출력