[백준_4963번] 섬의 개수 (python)

 

 

문제

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

4963번: 섬의 개수

 

나의 풀이_BFS

- visited를 사용하지 않고 풀이를 진행했다.

- tuple을 사용하여 꼭 deque에 ([(x,y)])를 해준다!

- 가로,세로,대각선을 모두 가기 때문에 8가지로 처리해준다

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

dx = [-1,1,0,0,-1,-1,1,1]
dy = [0,0,-1,1,1,-1,1,-1]
def bfs(x,y):
    arr[x][y] = 0 #방문했으니 0으로 처리해준다!
    queue = deque([(x,y)])

    while queue:
        x,y = queue.popleft()

        for i in range(8):
            nx = x+dx[i]
            ny = y+dy[i]

            if 0<=nx<h and 0<=ny<w:
                if arr[nx][ny] == 1:
                    arr[nx][ny] = 0
                    queue.append((nx,ny))

while True:
    w, h = map(int, input().split())
    if w == 0 and h==0 :
        break
    arr = []
    ans = 0
    visited = []

    for _ in range(h):
        arr.append(list(map(int, input().split())))
    for i in range(h):
        for j in range(w):
            if arr[i][j] == 1:
                bfs(i,j)
                ans +=1
    print(ans)