[백준] 2667번 단지번호붙이기,플러드필(Flood Fill)알고리즘 (Python)

문제 설명

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

플러드필(Flood Fill) 알고리즘 (a.k.a Seed fill)

이 문제를 풀기 위해서는 먼저 플러드필 알고리즘에 대해서 알아야 한다. 플러드필 알고리즘은 간단히 말해서 모든 정점에서 연결요소가 몇 개인지 파악하는 알고리즘이다. 픽셀 단위로 색을 칠할 때 사용한다.
DFS(거리우선탐색)을 활용한다.

나의 풀이

먼저, 입력값을 리스트를 이용하여 매트릭스 형태로 나타냈다. 입력값이 00001000과 같은 형태로 N개를 받아오는 형식이라 00001000을 String으로 받아와 슬라이싱한 후 int값으로 변환하여 매트릭스에 하나씩 넣어주었다.

dfs() 함수에서는 매트릭스의 크기를 넘거나, 방문 하였거나, 혹은 매트릭스 값이 1이 아닐 때(집이 없을 때) 리턴을 해주고, 그렇지 않으면 위-아래-좌-우 를 차례대로 재귀적으로 호출하도록 구현하였다. dfs()에서 return을 한다는 건 옮겨간 방향에서 조건이 맞지 않아 방향을 바꿈을 의미한다.

import sys

N = int(sys.stdin.readline())

matrix = [[0] * N  for _ in range(N)]
visited = [[0] * N  for _ in range(N)]

# 입력값 받아서 매트릭스로 표현
for i in range(N):
    sNum = sys.stdin.readline()
    for j in range(N):
        matrix[i][j] = int(sNum[j])

def dfs(i, j, vil_index):
    if(i < 0 or i >= N or j < 0 or j >= N or matrix[i][j] != 1 or visited[i][j] == 1):
        return  #리턴을 한다는 건 방향을 바꾼다는 뜻이다.
    else:
        visited[i][j] = 1 # visited check 가 여기 들어가야 함에 주의
        vil_index.append(1) # index check도 여기 들어와야 함에 주의
        dfs(i-1, j, vil_index)
        dfs(i+1, j, vil_index)
        dfs(i, j-1, vil_index)
        dfs(i, j+1, vil_index)

num_of_vil = 0
vil_list = []

# 방문하지 않은, 그리고 집이 있는 정점에 대하여 dfs() 수행
for i in range(N):
    for j in range(N):
        if(visited[i][j] == 0 and matrix[i][j] == 1):
            num_of_vil += 1
            vil_index = []
            dfs(i, j, vil_index)
            vil_list.append(len(vil_index))

print(num_of_vil)

for list in sorted(vil_list):
        print(list)