Koala - 15기/기초 알고리즘 스터디
[백준/Python] 4963번 : 섬의 개수
rlawjdgns02
2024. 8. 25. 23:15
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)