[BOJ] 섬의 개수

---

코드

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

def bfs(graph, sx, sy):
    q = deque([(sx, sy)])
    visited[sx][sy] = 1
    
    while q:
        x, y = q.popleft()
        for d in [(0,1), (0,-1), (1,0), (-1,0), (-1,-1), (-1,1), (1,-1), (1,1)]:
            nx, ny = x + d[0], y + d[1]
            if 0 <= nx < h and 0 <= ny < w:
                if graph[nx][ny] == 1 and not visited[nx][ny]:
                    visited[nx][ny] = 1
                    q.append((nx, ny))
    
while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0: 
        break

    graph = [list(map(int, input().split())) for _ in range(h)]
    visited = [[0]*w for _ in range(h)]
    ans = 0
    for i in range(h):
        for j in range(w):
            if not visited[i][j] and graph[i][j] == 1:
                bfs(graph, i, j)
                ans += 1
    print(ans)

결과

풀이 방법

• 3주간 군사교육을 받고 와서 그래프 알고리즘을 상기시킬 겸 기본문제를 풀이하였다. bfs로 해결하였다.

---