백준 알고리즘 - 섬의 개수 (4963) [Python]

 

 

 문제

 

www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

 

 

 

 

 

 문제 상황

 

- 이동할 수 있는 블록의 집합을 하나의 섬으로 보고, 섬의 총 개수를 구한다.

 

 

 

 

 

 

 해결 전략

 

- 간단한 dfs 문제이다. 순회하며 visited를 갱신하며 개수를 찾는다.

 

 

 

 

 

 

 코드

 

from sys import stdin,setrecursionlimit
setrecursionlimit(100000)
input = stdin.readline
def dfs(x,y):
    dy = [-1,0,1,-1,0,1,-1,0,1]
    dx = [-1,-1,-1,0,0,0,1,1,1]
    for i in range(9):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0<=xx<h and 0<=yy<w:
            if maps[xx][yy] == 1 and visited[xx][yy]==0:
                visited[xx][yy] = 1
                dfs(xx,yy)
        
while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0 : break 
    maps = [list(map(int, input().split())) for _ in range(h)] # 지도
    visited = [[0 for i in range(w)] for j in range(h)] # 방문 여부 표시
    islands = 0  # 섬의 개수
    for i in range(h):
        for j in range(w):
            if maps[i][j] == 1 and visited[i][j] == 0: # 지도에서 땅이고 아직 방문하지 않은 지역이라면
                visited[i][j] = 1
                dfs(i,j)
                islands += 1
    print(islands)

 

 

 

 

 

 

 

 

 해설

 

- 전체 지역을 순회하며 지도에서 땅을 의미하고, 방문하지 않은 지역일 경우 dfs를 시작한다. dfs를 통해 갈 수 있는 9방향을 검색하여 체크한다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- dfs에서 재귀 조건에 visited 여부를 다시 한번 체크하지 않아 무한 루프에 빠졌다. 이미 방문한 지역은 검색할 때에도 제외해주어야 한다.