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

4963번: 섬의 개수

 

>문제

>접근방법

결국 섬의 개수를 세는 거니까 정사각형을 전체에서 섬이 있는 곳을 발견 할 때마다 재귀 dfs로 탐색하고 발견하면 count를 1 더하면 된다. 재귀 dfs 함수 안에서는 상하좌우 대각선 네 방면까지 탐색하고 방문한 경우에는 0으로 바꿔준다.

 

 

>풀이법

   주석으로 대체

 

 

>코드

# 런타임 에러 (RecursionError) 방지
import sys
sys.setrecursionlimit(10**6)

# 좌표가 (0, 0)일 때를 기준으로 상하좌우, 대각선 네 방면까지 총 여덟번을 탐색하는 리스트
dx, dy = [-1, -1, -1, 0, 0, 1, 1, 1], [-1, 0, 1, -1, 1, -1, 0, 1]

def dfs_rec(x, y):
    island[x][y] = 0 # 방문 표시로 0 으로 바꿔준다.
    for i in range(8): # 상하좌우, 대각선까지 탐색한다.
        a, b = dx[i]+x, dy[i]+y # (x, y) 기준으로 상하좌우, 대각선의 인덱스를 a와 b에 대입
        
        # a와 b가 정사각형 내의 범위인지 확인하고 1일 경우에
        if 0 <= a < h and 0 <= b < w and island[a][b] == 1: 
            dfs_rec(a, b) # dfs 재귀적으로 탐색

# 정사각형 가로 세로 값이 0 0으로 입력될 때까지 무한 반복
while 1:
	# 너비와 세로를 입력받는다.
    w, h = map(int, input().split())
    count = 0 # 섬의 개수를 입력받을 변수
    
    # 입력값이 0 0 이면 종료한다.
    if w == 0 and h == 0:
        exit(0)
        
    # 섬의 정보를 입력받는다.
    island = [list(map(int, input().split())) for _ in range(h)]

	# 정사각형에서 섬이 있는 부분(1)을 찾으면 dfs함수를 수행하는 방식으로 섬의 개수를 카운트한다.
    for j in range(h):
        for k in range(w):
            if island[j][k] == 1:
                dfs_rec(j, k)
                count += 1
	# 섬의 개수 출력            
    print(count)

 

 

>결과

 

 

>결론 

엉뚱한 곳에서 indexerror가 계속 뜨길래 설마 dfs함수 내의 조건문에서 a, b 범위 검사하기 전에 island[a][b]로 먼저 사용되는게 원인인가... 싶어서 위치를 뒤로 옮겼더니 正解..