[파이썬 알고리즘 문제풀이] - Section7 / 깊이/넓이 우선 탐색(DFS, BFS) 활용 - 13

🎈 섬나라 아일랜드(BFS 활용)

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

만약 위와 같다면

▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다.
두 번째 줄부터 격자판 정보가 주어진다.

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

▣ 입력예제 1
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
5

import sys
# sys.stdin = open("input.text", "rt")
from collections import deque

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

cnt = 0
dq = deque()

dx = [1,-1,0,0,1,1,-1,-1]
dy = [0,0,1,-1,-1,1,-1,1] #대각선까지.


def BFS(a,b):
    global cnt
    dq.append((a,b)) #시작점 삽입
    g[a][b] = 0 #시작점 방문 표시
    #만약 각 연결요소 별 개수를 구해야 하면 시작점도 카운팅 해줘야함!
    
    while dq:
        x,y = dq.popleft()
        
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0<=nx<n and 0<=ny<n: #경계선
                if g[nx][ny] == 1: #아직 방문 전
                    g[nx][ny] = 0 #방문 표시 후
                    dq.append((nx,ny))
    #이렇게 BFS한번 하면 하나의 연결요소 찾고 끝난다.
    #그리고 큐에 좌표 x,y 튜플 형태로 넣는거 잊지말자.

for i in range(n):
    for j in range(n):
        if g[i][j] == 1:
            BFS(i,j)
            cnt += 1

print(cnt)                 

🎈 코멘트

이 문제 역시 연결요소 개수 구하기 문제. BFS를 한번 돌 때마다 연결요소 하나 찾는거야. 그리고 시작지점 삽입 후 방문 표시 해주는거 잊지말자. + 만약 각 연결요소의 개수를 구해야 하면 시작지점 카운팅도 해주고 출발해야해

• BFS 큐에 삽입 시에 좌표 x,y 튜플 형태로 넣자. (그냥 넣었다가 꺼낼때 에러뜸..)