[TIL] 99클럽 코테 스터디 6일차 TIL + 백준 4963 BFS

🌼 오늘의 문제 - 백준 4963. 섬의 개수

며칠 전에 풀었던 '안전 영역' 문제와 유사했다. 안전 영역은 상하좌우만 인접한 영역으로 봤지만, 섬은 대각선으로 이어져 있어도 하나의 영역으로 봤다. 그래서 유사하게 BFS를 활용하고자 했고, 갈 수 있는 방향을 상하좌우대각선으로 총 8군데를 방문하도록 했다. 문제를 시작하고 바로 풀이가 생각나서 금방 풀 수 있을 것 같았는데, 계속해서 답을 틀렸다. 하.. 도대체 뭐가 문제일까 여러 번 프린트를 찍고 확인해 봤지만 이해할 수 없는 visited 배열만이 나오고 있었다. 그러다가 48분쯤 되었을 때 결국 GPT에게 틀린 부분을 찾아달라고 했는데, 아니 글쎄..!!! visited[nx][ny]를 해야 하는데 visited[x][y]를 하고 있었다. visited 배열이 이상하다는 건 알았지만, 계속 True로 전환하는 위치가 이상한지만 확인했다. 실수를 알아차리지 못했다니.. 아쉽다..!

from collections import deque

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


def bfs(arr, visited, w, h, i, j):
    queue = deque()
    queue.append((i, j))

    while queue:
        x, y = queue.popleft()

        for i in range(8):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < h and 0 <= ny < w:
                if not visited[nx][ny] and arr[nx][ny] == 1:
                    visited[nx][ny] = True  # 여기 nx, ny를 x, y로 잘못 넣고 있었다..
                    queue.append((nx, ny))


def solution(w, h):
    arr = [list(map(int, input().split())) for _ in range(h)]
    visited = [[False] * w for _ in range(h)]
    count = 0

    for i in range(h):
        for j in range(w):
            if not visited[i][j] and arr[i][j] == 1:
                bfs(arr, visited, w, h, i, j)
                count += 1

    print(count)


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

    solution(w, h)