백준 / 섬의 개수 / 4963

Question

문제링크
Silver 5

Logic

기본 구조 : bfs
1. 상하좌우, 대각선을 탐색하기 위해 dx, dy를 정의한다.
2. 주어진 초기 그래프를 탐색하며, 1을 만나면 bfs를 작동시킨다.
3. bfs 내에선 1과 맞닿아있는 1을 모두 0으로 바꿔버린다.
4. 모든 그래프 내 데이터가 0이 되었다면 bfs가 작동된 횟수를 출력한다.
5. 0,0이 출력되기 전까지 이 과정을 반복한다.

Code

from collections import deque
from sys import stdin

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

def bfs(a,b):
    global w,h
    global li
    queue = deque()
    queue.append([a,b])
    li[a][b] = 0

    while queue:
        x,y = queue.popleft()
        for i in range(8):
            xx = x+dx[i]
            yy = y+dy[i]
            if 0 <= xx < h and 0 <= yy < w and li[xx][yy] == 1:           
                li[xx][yy]=0
                queue.append([xx,yy])


while True:
    count=0
    w,h = map(int,stdin.readline().split())
    if w==0 : break
    li=[]
    for _ in range(h):
        li.append([int(i) for i in stdin.readline().split()])

    for i in range(h):
        for j in range(w):
            if li[i][j]==1:
                bfs(i,j)
                count+=1

    print(count)