문제 - 생략
문제풀이
import sys
from collections import deque
sys.stdin=open("input.txt", "r")
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): #range의 범위만큼 자식이 생긴다
x=tmp[0]+dx[k]
y=tmp[1]+dy[k]
if 0<=x<n and 0<=y<n and board[x][y]==1: #xx,yy좌표는 방문한 적이 없어야 한다.
board[x][y]=0 #자식을 방문한 경우 발자국을 남긴다.
Q.append((x, y))
cnt+=1
print(cnt)
해설
▶ 12시 방향, 6시 방향, 3시 방향, 9시 방향과 더불어 4개의 대각선방향까지 고려한다.
따라서 next좌표는 8개가 된다.
▶ Q(큐)가 0이 되었을 때는 더 이상 이동할 좌표가 없다는 것을 의미하므로 해당 섬을 다 탐색했음을 의미한다.
▶ 결과적으로 Q가 0이 되어 while문이 종료되었을 때 하나의 섬 탐색이 끝난다. 이때 cnt 를 +1증가시켜 준다.
▶ 이중 for문을 돌면서 넓이우선탐색(BFS)을 할 수도 있다.
'파이썬 알고리즘 > DFS, BFS 활용' 카테고리의 다른 글
15.토마토(BFS 활용) (0) | 2022.11.11 |
---|---|
14. 안전영역(BFS) vs 안전영역(DFS) (0) | 2022.11.11 |
12.단지 번호 붙이기(DFS) (0) | 2022.11.11 |
11. 등산경로(DFS) (0) | 2022.11.11 |
10.미로탐색(DFS) - 섹션6의 순열구하기 문제참고 (0) | 2022.11.11 |