728x90
분석
[2667] 단지번호붙이기(BFS)
2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를
karla.tistory.com
[17472] 다리 만들기2 (BFS, MST)
17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바
karla.tistory.com
풀이
"""
섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있음. 0은 바다
섬나라 아일랜드에 몇 개의 섬이 있는지
첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다. 두 번째 줄부터 격자판 정보가 주어진다.
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
"""
import sys
input=sys.stdin.readline
from collections import deque
# 여덟 방향 탐색을 위한 상수
dr=[0,1,0,-1,-1,1,1,-1]
dc=[1,0,-1,0,1,1,-1,-1]
n=int(input())
graph=[list(map(int, input().split())) for _ in range(n)]
# print(graph)
def BFS(i,j):
global cnt
queue=deque()
graph[i][j]=0
queue.append([i,j])
while queue:
print(queue)
r,c=queue.popleft()
for d in range(8): # 네방향+대각선
nextX= r+dr[d]
nextY= c+dc[d]
if 0<=nextX<n and 0<=nextY<n and graph[nextX][nextY]==1:
graph[nextX][nextY] = 0 # 방문표시, 바다로 만듬
queue.append([nextX, nextY])
cnt+=1
cnt=0
# 구분 작업 수행
for i in range(n):
for j in range(n):
if graph[i][j]==1:
BFS(i,j)
print(cnt)
728x90