[BOJ][Python] 4963 섬의 개수

Overview

• 체감 난이도: ★★☆☆☆
• 문제 레벨: 실버 2
• 문제 유형: BFS
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

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

 

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

 

 

✔︎ BFS 기본 문제와 다른 점은 대각선으로 이동이 가능하다고 친다는 것이다. 

 

[코드]

from collections import deque


def in_range(x, y):
    return 0 <= x < h and 0 <= y < w


def can_go(x, y):
    return in_range(x, y) and not visited[x][y] and arr[x][y] == 1


def bfs():
    dxs, dys = [1, 0, -1, 0, 1, 1, -1, -1], [0, 1, 0, -1, 1, -1, 1, -1]

    while q:
        cx, cy = q.popleft()
        for dx, dy in zip(dxs, dys):
            nx, ny = cx + dx, cy + dy

            if can_go(nx, ny):
                q.append((nx, ny))
                visited[nx][ny] = True


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

    arr = [list(map(int, input().split())) for _ in range(h)]
    visited = [[False] * w for _ in range(h)]
    q = deque()

    cnt = 0
    for i in range(h):
        for j in range(w):
            if not visited[i][j] and arr[i][j] == 1:
                visited[i][j] = True
                q.append((i, j))
                bfs()
                cnt += 1

    print(cnt)