[BOJ 4963] 섬의 개수(Python)

문제

섬의 개수

---

문제 해설

이 문제는 BFS와 DFS로 풀 수 있으며 4방탐색이 아닌 8방 탐색을 활용해야 합니다. 풀이과정은 다음과 같습니다.

1. 이중 for문을 이용하여 그래프 전체를 탐색합니다.
2. 1을 발견하면 answer +1. DFS 혹은 BFS 탐색을 진행하여 만나는 모든 1을 0으로 바꿔줍니다. 이때 4방향이아닌 8방향으로 탐색해야 합니다.
3. 1~2 반복

---

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline
# 섬의 개수를 세서 반환
def count_island(r, c, graph):
    dx = -1, -1, 0, 1, 1, 1, 0, -1
    dy = 0, 1, 1, 1, 0, -1, -1, -1
    answer = 0
    q = deque()
    for i in range(r):
        for j in range(c):
            if graph[i][j] == 1:
                answer += 1
                q.append([i, j])
                graph[i][j] = 0
                while q:
                    x, y = q.popleft()
                    for k in range(8):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if 0 <= nx < r and 0 <= ny < c and graph[nx][ny] == 1:
                            q.append((nx, ny))
                            graph[nx][ny] = 0
    return answer


while True:
    c, r = map(int, input().split())
    if c == 0 and r == 0:
        break
    graph = []
    for _ in range(r):
        graph.append(list(map(int, input().split())))
    print(count_island(r, c, graph))

---