[백준_파이썬]4963_섬의 개수

www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

내 풀이

from collections import deque

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


def bfs(x, y):
    q = deque()
    q.append((x, y))
    # maps[x][y] = 0
    while q:
        x, y = q.popleft()

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

            if nx >= 0 and nx < h and ny >= 0 and ny < w:
                if maps[nx][ny] == 1:
                    maps[nx][ny] = 0
                    q.append((nx, ny))


while True:
    w, h = map(int, input().split())
    # 종료조건
    if w == 0 and h == 0:
        break

    # maps정보 받기
    maps = []
    cnt = 0
    for i in range(h):
        maps.append(list(map(int, input().split())))

    for i in range(h):
        for j in range(w):
            if maps[i][j] == 1:
                cnt += 1
                bfs(i, j)
    print(cnt)

    # print(*maps, sep="\n")

대각선으로 섬을 이동할 수 있으므로 dx, dy에 대각선으로 이동가능한 경우도 추가해줬다.
많이 풀어보면 감이 올 텐데, 한동안 다른 챕터 푸느라 DFS/BFS쪽을 안풀어봤더니 감이 없어졌다.. 

다시 열심히 골고루 풀어보자 :)