Algorithm - 섬나라 아일랜드(BFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[섬나라 아일랜드(BFS)]

 

섬나라 아일랜드의 지도가 격자판의 정보로 주어진다.

각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다이다. 

섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하시오.

 

지도

 

 

*입력 설명

첫 번째 줄에 자연수 N(3 ≤ N ≤ 20)이 주어진다.

두 번째 줄부터 격자판 정보가 주어진다.

 

*출력 설명

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

 

 

---

 

 

풀이(Python)

답안

import sys
from collections import deque
sys.stdin = open('AA/input_68.txt', 'rt')

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

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

for i in range(n):
    for j in range(n):
        if board[i][j] == 1:
            board[i][j] = 0
            Q.append((i, j))
            while Q:
                tmp = Q.popleft()
                for k in range(8):
                    x = tmp[0] + dx[k]
                    y = tmp[1] + dy[k]
                    if 0 <= x < n and 0 <= y < n and board[x][y] == 1:
                        board[x][y] = 0
                        Q.append((x, y))
            cnt += 1
print(cnt)

# 출력 : 5

 

input_68.txt(입력)

7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0

 

 

중요내용

1. 이 문제에서 BFS 탐색은 상하좌우 + 4방향의 대각선 탐색을 모두하는 8방향 탐색이다. (단, 탐색순서는 시계방향으로 이루어짐)
2. 이중 for문을 통해 2차원의 지도에서 행단위로 1을 찾으면, 그 위치에서 부터 BFS 탐색이 시작된다.
3. 한 번 탐색한 좌표는 해당 값을 0으로 만들어줘야 한다. (중복탐색 방지)
4. 큐 자료구조에 데이터를 넣을 때에는 튜플 형태로 넣어준다. (좌표로 활용하기 위함)
5. while 문에서 큐 자료구조를 통해 8방향의 BFS 탐색을 하면서, 섬의 개수를 카운팅하는 구조이다. 
6. 변수 x와 y는 앞으로 BFS 탐색을 진행할 방향을 의미한다.