[인프런] 섬나라 아일랜드

---

문제설명

섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다이다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하라.

 

입력조건

• 첫 줄에 자연수 N(3 <= N <= 20)이 주어진다.
• 둘째 줄부터 격자판 정보가 주어진다.

출력조건

• 첫 줄에 섬의 개수를 출력한다.

사고과정

• 단지 번호 붙이기 문제랑 비슷한 유형이다. 이것도 DFS/BFS 둘 다 활용해서 풀 수 있는 문제이다. 

풀이

- 한 소스코드 안에 dfs, bfs로 풀어보는 풀이 둘 다 작성했다.

from collections import deque

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]

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

def bfs(x, y):
    board[x][y] = 0
    queue = deque([(x, y)])
    while queue:
        x, y = queue.popleft()
        for i in range(len(dx)):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 1:
                board[nx][ny] = 0
                queue.append((nx, ny))
    return

def dfs(x, y):
    board[x][y] = 0
    for i in range(len(dx)):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 1:
            dfs(nx, ny)

cnt = 0
for i in range(n):
    for j in range(n):
        if board[i][j] == 1:
            dfs(i, j)
            cnt += 1
print(cnt)