백준 - 단지번호붙이기 (DFS/BFS) / Silver 1 / 2667번

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

2667번: 단지번호붙이기

 

풀이

import sys

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

city_map = []
result = []
global cnt
cnt = 0

for _ in range(n):
    temp = list(sys.stdin.readline())
    temp.pop()
    city_map.append(temp)


def dfs(row, col):
    global cnt
    cnt += 1
    city_map[row][col] = '0'

    if row > 0 and city_map[row-1][col] == '1':
        dfs(row - 1, col)
    if row < n-1 and city_map[row+1][col] == '1':
        dfs(row + 1, col)
    if col > 0 and city_map[row][col-1] == '1':
        dfs(row, col - 1)
    if col < n-1 and city_map[row][col + 1] == '1':
        dfs(row, col + 1)

    return


for i in range(n):
    for j in range(n):
        if city_map[i][j] == '1':
            dfs(i, j)
            result.append(cnt)
            cnt = 0

result.sort()
print(len(result))
for i in result:
    print(i)

전형적인 DFS/BFS 문제이다. 재귀를 이용하여 DFS방식으로 풀었으며

호출되는 dfs 함수 내에서 cnt 값을 공유하기 위해 전역 변수를 사용하였다.

 

그렇게 푼 후 더 좋은 코드가 없을까 고민하던중

전역 변수인 cnt 사용으로 dfs함수 선언 위치가 애매하여 가독성을 해친다고 생각되었고

또한 전역변수 사용을 최대한 지양하는 것이 좋다고 생각하여

다음과 같이 count 변수를 인자로 넣어주는 방식으로 리팩토링 하였다.

 

import sys


def dfs(row, col, count):
    count += 1
    city_map[row][col] = '0'

    if row > 0 and city_map[row - 1][col] == '1':
        count = dfs(row - 1, col, count)
    if row < n - 1 and city_map[row + 1][col] == '1':
        count = dfs(row + 1, col, count)
    if col > 0 and city_map[row][col - 1] == '1':
        count = dfs(row, col - 1, count)
    if col < n - 1 and city_map[row][col + 1] == '1':
        count = dfs(row, col + 1, count)

    return count


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

city_map = []
result = []

for _ in range(n):
    temp = list(sys.stdin.readline())
    temp.pop()
    city_map.append(temp)

for i in range(n):
    for j in range(n):
        if city_map[i][j] == '1':
            result.append(dfs(i, j, 0))

result.sort()
print(len(result))
for i in result:
    print(i)