[백준/Python] 4963번 : 섬의 개수

https://www.acmicpc.net/problem/4963

문제 풀이

1. r과 c를 입력받기 + 0 0 을 입력받는 순간 탈출\

2. arr 리스트에 섬의 상황 입력하기

3. 비교를 위한 check 리스트 생성

4. arr 전체를 돌며 flood_fill 함수 실행

5. flood_fill 함수가 끝나면 섬 1개를 의미하므로 cnt 1 증가

flood_fill 함수

대각선까지 감안하여야 하므로 x,y에 더해줄 d 생성

함수의 인자인 x,y에 맞는 nx, ny에 맞게 수정 -> 추가 flood_fill 실행

 

문제 코드

def flood_fill(x, y):        
    for i in range(len(d)):
        nx, ny = x + d[i][0], y + d[i][1]
        if 0 <= nx < r and 0 <= ny < c and arr[nx][ny] == 1 and not check[nx][ny]:
            check[nx][ny] = 1
            flood_fill(nx, ny)

import sys
sys.setrecursionlimit(10 ** 6)

d = [(-1, -1), (-1, 1), (1, -1), (1, 1), (-1, 0), (1, 0), (0, -1), (0, 1)]
while True:
    c, r = map(int, input().split())
    if r == 0 and c == 0:
        break
    arr= []
    for i in range(r):
        arr.append(list(map(int, input().split())))

    cnt = 0
    check = [[0] * c for _ in range(r)]

    for i in range(r):
        for j in range(c):
            if arr[i][j] == 1 and check[i][j] == 0:
                check[i][j] = 1
                flood_fill(i,j)
                cnt += 1
    print(cnt)