백준
백준 4963번: 섬의 개수
2호0
2021. 5. 20. 21:07
4963번: 섬의 개수
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
from collections import deque
graph = []
dx = [-1,1,0,0,-1,1,-1,1]
dy = [0,0,-1,1,1,-1,-1,1]
def apt(y,x):
que = deque()
que.append((x,y))
if graph[x][y]== 0:
return False
while que:
x,y = que.popleft()
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if nx<0 or ny<0 or nx>=m or ny>=n:
continue
if graph[nx][ny]==0:
continue
if graph[nx][ny]==1:
que.append((nx,ny))
graph[x][y]=0
graph[nx][ny]=0
return True
while True:
n, m = map(int, input().split())
count = 0
graph = []
if n==0 and m==0:
exit(0)
for _ in range(m):
graph.append(list(map(int,input().split())))
for h in range(m):
for w in range(n):
result=apt(w,h)
if result == True:
count += 1
print(count)
|
cs |