백준 4963 : 섬의 개수

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

4963번: 섬의 개수

1. 기본 중의 기본

 BFS, DFS로 탐색을 하거나 그래프 연결관계를 만들어서 풀거나 가장 기본적인 지식을 적용해 볼 수 있는 문제. 이번에는 BFS로 풀었다. 다음엔 DFS와 그래프 이론으로 풀어봐야겠다.

2. 전체코드

 메모리 : 115968 KB, 시간 : 180 ms, 풀이 시간 : 10 min

# 상, 하, 좌, 우, 상좌, 상우, 하좌, 하우
dx = [-1, 1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]
def bfs():
    visited = [[False for _ in range(w)] for _ in range(h)]
    result = 0
    for i in range(h):
        for j in range(w):
            if board[i][j] != 0 and not visited[i][j] :
                q = [[i, j]]
                visited[i][j] = True
                result += 1
                while q :
                    x, y = q[0]
                    del q[0]
                    for d in range(8):
                        nx = x + dx[d]
                        ny = y + dy[d]
                        if 0 <= nx < h and 0 <= ny < w and not visited[nx][ny] :
                            if board[nx][ny] == 1 :
                                visited[nx][ny] = True
                                q.append([nx, ny])
    return result

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

for i in range(len(res)):
    print(res[i])