[백준] 4963번 섬의 개수

💡문제접근

• "한 정사각형과 가로, 세로, 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다." 옮길 수 있는 경로를 가로, 세로 뿐만 아니라 대각선도 추가해줘야 한다.
• w와 h를 헷갈려서 계속 WA를 받았다.

💡코드(메모리 : 34128KB, 시간 : 76ms)

from collections import deque

import sys
input = sys.stdin.readline

def BFS(graph, a, b):
    queue = deque()
    queue.append([a, b])
    graph[a][b] = 0
    while queue:
        a, b = queue.popleft()
        dx = [0, 1, 1, 1, 0, -1, -1, -1]
        dy = [-1, -1, 0, 1, 1, 1, 0, -1]
        for t in range(8):
            na = a + dx[t]
            nb = b + dy[t]
            if na < 0 or na >= h or nb < 0 or nb >= w:
                continue
            if 0 <= na < h and 0 <= nb < w and graph[na][nb] == 1:
                graph[na][nb] = 0
                queue.append([na, nb])

while True:
    w, h = map(int, input().strip().split())
    if w == 0 and h == 0:
        break

    Map = []
    cnt = 0
    for _ in range(h):
        Map.append(list(map(int, input().strip().split())))

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

---

* 2차원 배열의 상하좌우 이동

※ (9시 방향 기준으로 반시계방향으로 돌았을 때)

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

* 2치원 배열의 상하좌우 + 대각선 이동

※ (9시 방향 기준으로 반시계방향으로 돌았을 때)

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

• graph[na][nb] → na의 값은 세로(h값), nb의 값은 가로(w값)

💡소요시간 : 37m