[ baekjoon ] 섬의 개수 4963번 ( python )

문제

백준 4963 섬의 개수 풀이 ( 파이썬 )

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

4963번: 섬의 개수

 

풀이

일단 보통 문제는 4방향으로 dx, dy를 지정하지만 이 문제는 대각선도 연결된 것으로 보므로 8방향으로 초기화해야 한다.

입력을 다 받고나서

탐색을 진행하는데 1인 부분을 찾을 때마다 dfs를 이용하고 방문처리를 진행한다.

from collections import deque
import sys
 
sys.setrecursionlimit(10**9)
 
dx=[-1,-1,0,1,1,1,0,-1]
dy=[0,1,1,1,0,-1,-1,-1]
 
 
while True:
    r,c=map(int,input().split())
    if r==0 and c==0:
        break
    arr=[]
 
    # 입력
    for i in range(c):
        arr.append(list(map(int,input().split())))
 
    
    visited=[[False]*r for _ in range(c)]
    cnt=0
 
    def dfs(x,y):
        visited[x][y]=True
 
        for i in range(8):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or ny<0 or nx>=c or ny>=r:
                continue
            if arr[nx][ny]==1 and not visited[nx][ny]:
                dfs(nx,ny)
 
        return
 
    # 1인 부분 찾을 때 마다 dfs
    for i in range(c):
        for j in range(r):
            if arr[i][j]==1 and not visited[i][j]:
                dfs(i,j)
                cnt+=1
    
    print(cnt)