[ 백준 / 파이썬 ] 4963. 섬의 개수

 

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

4963번: 섬의 개수

🎉🎉 문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

 

 

🎉🎉 풀이

✅ 개수 탐색하는 문제 나오면 무조건 dfs로 푸는 버릇이 있다. . .

✅ 그러나 오늘도 어김없이 재귀 깊이 제한 안 풀어줘서 RecursionError 맞았고요

import sys
sys.setrecursionlimit(10000)

꼭 빼먹지 말자

 

✅ 일반적인 구역 구하기 문제인데 8방향을 탐색해야 한단 점만 다르다

 

 

🎉🎉 코드

import sys
sys.setrecursionlimit(10000)

def dfs(ground, visited, i, j, w, h):
    visited[i][j] = True

	#12시 방향부터 시계방향으로 돌았을 때 좌표
    di = [-1, -1, 0, 1, 1, 1, 0, -1]
    dj = [0, 1, 1, 1, 0, -1, -1, -1]

    for k in range(8):
        ni = i+di[k]
        nj = j+dj[k]

		#범위 안에 있고, 건너갈 수 있는데 방문 전인 섬이라면 이어져 있다
        if 0 <= ni < h and 0 <= nj < w:
            if not visited[ni][nj] and ground[ni][nj] == 1:
                dfs(ground, visited, ni, nj, w, h)



while True:
    w, h = map(int, input().split())

	#종료 시 0 0이 입력된다
    if w == 0 and h == 0:
        break

    ground = [list(map(int, input().split())) for _ in range(h)]

    visited = [[False]*w for _ in range(h)]

    cnt = 0 #섬의 개수
    for i in range(h):
        for j in range(w):
            #아직 탐색하지 않은 섬이라면
            if not visited[i][j] and ground[i][j] == 1:
            	#이어진 섬 탐색
                dfs(ground, visited, i, j, w, h)
                #섬의 개수 추가
                cnt += 1

    print(cnt)