.PNG)
67. 섬나라 아일랜드(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
<내 풀이>
(1) 오류존재한다, 어떤 부분이 잘못된건 지 검토 필요
===>ㅋㅋ..dx,dy가 8개씩인데 6개라고 함
==>그리고 dx,dy에 dx[-1,-1] dy[1,1]로 추가했던 부분있음 ㅂㄷㅂㄷ
이런 사소한 부분에서 정신 차리자 제발
from collections import deque
dx=[-1,0,1,0,1,-1,-1,-1]
dy=[0,1,0,-1,1,1,1,-1]
n=int(input())
a=[(list(map(int, input().split()))) for _ in range(n)]
q=deque()
cnt=0
for i in range(n) :
for j in range(n) :
if a[i][j]==1:
q.append((i,j))
cnt+=1
print(q)
while q:
k=q.popleft()
for i in range(6) :
xx=k[0]+dx[i]
yy=k[1]+dy[i]
if 0>xx or xx>=n or yy<0 or yy>=n or a[xx][yy]==0 :
continue
a[xx][yy]=0
q.append((xx,yy))
print(cnt)
(2)
from collections import deque
dx=[-1,0,1,0,1,1,-1,-1]
dy=[0,1,0,-1,1,-1,1,-1]
n=int(input())
a=[(list(map(int, input().split()))) for _ in range(n)]
q=deque()
cnt=0
for i in range(n) :
for j in range(n) :
if a[i][j]==1:
q.append((i,j))
cnt+=1
print(q)
while q:
k=q.popleft()
for i in range(8) :
xx=k[0]+dx[i]
yy=k[1]+dy[i]
if 0>xx or xx>=n or yy<0 or yy>=n or a[xx][yy]==0 :
continue
a[xx][yy]=0
q.append((xx,yy))
print(cnt)
<풀이>
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):
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)
<반성점>
- 사소한 거에서 실수하지 말자
<배운 점>
- 성립 안되는 조건들에 걸리면 continue에 걸려서 밑에 있는 것들 무시하고 위로,
아니라면 밑에 있는 것들까지 체크
if 0>xx or xx>=n or yy<0 or yy>=n or a[xx][yy]==0 :
continue
a[xx][yy]=0
q.append((xx,yy))
