[파이썬, Python] 백준 4963: 섬의 개수

문제

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

4963번: 섬의 개수

코드

import sys
sys.setrecursionlimit(10**6)

dx = [1, 1, -1, -1, 1, -1, 0, 0]
dy = [0, 1, 0, 1, -1, -1, 1, -1]

def dfs(x, y):
    land[x][y] = 0
    
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0 <= nx < h and 0 <= ny < w and land[nx][ny] == 1:
            dfs(nx, ny)

while True:
    w, h = map(int, input().split())
    
    if w == 0 and h == 0:
        break
        
    land = list(list(map(int, input().split())) for i in range(h))
    
    cnt = 0
    
    for i in range(h):
        for j in range(w):
            if land[i][j] == 1:
                dfs(i, j)
                cnt += 1
            
    print(cnt)

설명

dfs를 이용해서 풀이했다.

우선 8방향을 모두 방문해야 하기에 그에 맞춰서 dx, dy를 설정해 주었다.

이제 그에 맞춰 dfs를 진행한다.

우선 방문한 땅을 0으로 변경해서 추가로 방문하지 않도록 한다.
그리고 8방향을 탐색한다.
만약 해당 수가 땅의 범위를 넘어가거나 땅이 아니라면(1이 아니라면) 탐색하지 않는다.
그 외에 조건에 맞는 수라면 탐색을 진행한다.

입력 조건의 경우 w와 h를 각각 받아주고,
두 수가 모두 0이면 break 해주었다.

땅의 경우 리스트로 받아주고
섬의 개수를 세기 위한 cnt도 만들어준다.

이후 h와 w를 고려하고 땅이 존재하는 경우 dfs를 진행해 준다.

최종적으로 카운트된 섬의 개수를 출력한다.