문제
정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.
한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.
dx = [-1, 1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]
def dfs(x, y, visited):
if visited[y][x] == False:
visited[y][x] = True
if graph[y][x] == 1:
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= w or ny >= h:
continue
dfs(nx, ny, visited)
return True
return False
w, h = map(int, input().split())
while w != 0 and h != 0:
graph = []
for _ in range(h):
graph.append(list(map(int, input().split())))
visited = [[False] * w for _ in range(h)]
count = 0
for i in range(h):
for j in range(w):
if dfs(j, i, visited) == True:
count += 1
print(count)
w, h = map(int, input().split())상하좌우만 보면 기존 문제들과는 다르게 대각선도 고려해야 한다.
