[백준] 4963번_섬의개수

Study/알고리즘

[백준] 4963번_섬의개수

혤리 2020. 2. 21. 23:42

문제 링크 : https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는

www.acmicpc.net

import sys
sys.setrecursionlimit(10000)

dx = [0,0,1,-1,1,1,-1,-1]
dy = [1,-1,0,0,1,-1,1,-1]

def dfs(x,y):
    a[x][y] = 0
    for i in range(8):
        nx,ny = x+dx[i],y+dy[i]
        if 0<=nx<h and 0<=ny<w and a[nx][ny] == 1:
            dfs(nx,ny)


while True:
    w,h = map(int,input().split())
    if w==h==0:
        break
    cnt = 0
    a = [list(map(int,input().split())) for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if a[i][j] == 1:
                dfs(i,j)
                cnt += 1
    print(cnt)