[백준] 4693번 섬의 개수 파이썬 정답 코드

4963번: 섬의 개수

---

1. 문제 내용

 

 

2. 접근 방식

• 대각선까지 고려해야 한다.

상하좌우를 고려하는 기존 너비 우선 탐색 방식에서 대각선만 추가로 고려하면 된다. 따라서 파란색 별의 위치를 (0, 0)이라면, 상하좌우를 포함한 대각선까지 포함하는 모든 좌표들을 directions 리스트에 담아서 탐색하자. 

 

 

3. 정답 코드

from collections import deque

while True:
    def count_island(a, b):
        queue = deque([[a, b]])
        visited[a][b] = True

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

            for d in directions:
                dx = x + d[0]
                dy = y + d[1]

                if dx >= h or dx < 0 or dy >= w or dy < 0:
                    continue

                if not visited[dx][dy] and graph[dx][dy]:
                    visited[dx][dy] = True
                    queue.append([dx, dy])


        return 1


    w, h = map(int, input().split())

    if w == 0 and h == 0:
        break

    graph = [list(map(int, input().split())) for _ in range(h)]
    visited = [[False] * w for _ in range(h)]
    directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]

    count = 0
    for i in range(h):
        for j in range(w):
            if not visited[i][j] and graph[i][j]:
                count += count_island(i, j)

    print(count)