[BFS 알고리즘] 섬의 개수

기출:  BOJ #4963

 

일반적인 BFS문제와 다른 점은 다음과 같다

 

1. 입력 종료 조건은 "0 0"의 입력이다

2. 같은 섬의 조건은 대각선을 포함한다

 

입력을 미리 받아 놓으려면 (입력의 개수가 정해지지 않은 경우)

sys.stdin.readline() 함수를 사용하면 된다

 

from sys import stdin

lines = stdin.readlines()

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

while lines:
    y, x = map(int,lines.pop(0).split())
    if y==0 and x==0: break
    ans = 0
    visited = [[False for __ in range(y)] for _ in range(x)]
    board = list()
    for i in range(x):
        board.append(list(map(int,lines.pop(0).split())))
    for i in range(x):
        for j in range(y):
            if not visited[i][j] and board[i][j] == 1:
                # BFS
                visited[i][j] = True
                queue = [[i,j]]
                while queue:
                    cur = queue.pop(0)                                
                    for dir in range(8):
                        mx = cur[0] + dx[dir]
                        my = cur[1] + dy[dir]
                        if mx<0 or my<0 or mx>=x or my>=y: continue
                        if board[mx][my]==0: continue
                        if visited[mx][my]: continue
                        visited[mx][my] = True
                        queue.append([mx,my])
                ans += 1
    print(ans)