BOJ - 4963

백준 문제 링크
섬의 개수

❓접근법

1. BFS 방식을 사용했다.
2. 이번에는 dx,dy 테크닉을 상,하,좌,우 가 아닌 대각선까지 고려해야한다.
3. BFS 코드는 전에 올린 게시글 '유기농 배추'문제와 유사하다.
4. for문으로 섬과 바다 지도를 돌면서, 상,하,좌,우,대각선을 다 살펴서 1이라면 0으로 만들고, 좌표를 함수에 넣어서 count를 구해줬다.
5. 우리가 구하고자 하는 것은 count가 아닌, count의 개수이므로 temp에 count를 넣어주고, 반복문 밖에서 answer에 len(temp)를 넣어줬다.

👌🏻코드

from collections import deque


def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    
    dx = [0,0,1,-1,-1,1,-1,1] # 대각선까지 고려
    dy = [1,-1,0,0,1,1,-1,-1]
    
    count = 0
    
    lst[x][y] = 0 # visited의 역할
    
    while queue:
        x,y = queue.popleft()
        count += 1
        
        for d in range(8):
            nx = x + dx[d]
            ny = y + dy[d]
            
            if (0<=nx<h) and (0<=ny<w) and (lst[nx][ny] == 1):
                lst[nx][ny] = 0
                queue.append((nx,ny))
                
    return count
        


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

    temp = []
    for i in range(h):
        for j in range(w):
            if lst[i][j] == 1:
                count = bfs(i,j)
                temp.append(count)
    answer.append(len(temp))
    
    
for i in answer:
    print(i)