[백준/BOJ] - 4963번 python 풀이 - DFS

---

Key Point 

1. 가로, 세로 뿐만 아니라 대각선 까지 섬 하나라 인정한다고 했으므로 dx, dy list 선언할 때 고려

2. 육지인 위치에 도착하면 상하좌우 대각선 모두 육지 존재 여부 확인 후 있을 경우 재귀함수 호출 후 같은 동작 반복

 

알게 된 점

1. sys.setrecursionlimit을 통해 재귀 limit을 걸어줄 수 있다.

 

---

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) #재귀 limit 걸어주기
dx = [1, -1, 0 ,0, -1, -1, 1, 1] #대각선도 인정하는거 인지
dy = [0 ,0 , 1, -1, -1, + 1, -1, 1] 
cnt = 0

def dfs(x,y):
    global cnt    
    mapp[x][y] = 0 #방문 처리
    for i in range(8): #상하좌우 대각선 전부 순회
        nx = x + dx[i] 
        ny = y + dy[i]

        if (0<=nx<m) and (0<=ny<n): #초과 범위 할당
            if(mapp[nx][ny] == 1): #미방문일 때
                dfs(nx,ny) #재귀적 호출

n=1
m=1
mapp = []
while True:
    n, m = map(int, input().split()) #너비 높이
    if n == 0 and m == 0: #입력이 0,0 일 경우 종료
        exit(0)
    for _ in range(m):
        mapp.append(list(map(int, input().split())))    
    for i in range(m):
        for j in range(n):            
            if mapp[i][j] == 1:                
                dfs(i, j)
                cnt+=1 #dfs 빠져 나오면 섬 하나 count
    print(cnt)                 
    cnt = 0
    mapp.clear() #case 당 리스트를 클리어한다.