[BOJ] 2667번 : 단지 번호 붙이기

1. 문제

2667번: 단지번호붙이기

1. 인접한 집들의 단지 구성하기
2. 인접 : 상하좌우 (대각선 포함안함)
3. 각 단지의 집 수를 오름차순 출력하기
4. 1 : 집
5. 0 : 집 없는 곳

2. 알고리즘

1. dfs로 단지파악하기
2. 집일 경우 count + 1

3. 소스코드

n = int(input()) # n * n 행렬
graph = [list(map(int, input())) for _ in range(n)]

# 상하좌우 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

apart = [] # 각 단지별 집 수 저장
count = 0 # 집 수 저장

# 단지 파악
def dfs(x, y):
    global count

    # 행렬 범위 벗어나는 경우
    if x < 0 or y < 0 or x >= n or y >= n:
        return False

    # 집인 경우
    if graph[x][y] == 1:
        graph[x][y] = 0 # 방문 처리
        count += 1 # 집 개수 카운트

        # 상하좌우 이동
        for i in range(4):
            dfs(x + dx[i], y + dy[i])
        return True

    return False

# 모든 요소에 대해서 탐색
for i in range(n):
    for j in range(n):
        if dfs(i, j):
            # 탐색이 끝나면 해당 단지에 대해서 집의 개수가 count에 저장된다.
            apart.append(count)
            count = 0 # count 초기화

apart.sort() # 오름차순 정렬
print(len(apart), *apart, sep='\n') # 개행출력

4. 파이썬 - global

왜 count는 global 키워드를 사용하고 graph는 global 키워드를 사용하지 않았을까?

파이썬에서 mutable object에 대해서는 global 키워드가 필요없기 때문이다. 그렇다면 mutable object는 무엇일까?

1) mutable object

출처. Understanding Mutable and Immutable in Python

mutable object의 정의는 내부 상태를 바꿀 수 있는 객체를 말한다. mutable object와 immutable object의 종류는 다음과 같다.

Objects of built-in type that are mutable are:

• Lists
• Sets
• Dictionaries
• User-Defined Classes (It purely depends upon the user to define the characteristics)

Objects of built-in type that are immutable are:

• Numbers (Integer, Rational, Float, Decimal, Complex & Booleans)
• Strings
• Tuples
• Frozen Sets
• User-Defined Classes (It purely depends upon the user to define the characteristics)

2) 주의 사항

data = ['a', 'b', 'c']

def f():
	data = data + [1, 2, 3]
	return data

print(f())

위 코드에 경우에 data는 mutable object인 list이기 때문에 문제없어 보이지만 이것은 내부 상태를 변경하는 것이 아닌 동일한 이름의 data라는 local variable을 만드는 것이다. 따라서 + 연산에 사용된 data가 ['a', 'b', 'c'] 요소를 가진 외부 data 변수가 아닌 함수 f()내에서 찾으므로 UnboundLocalError가 발생한 것이다.