[백준 2667번] 단지번호붙이기 - Python

문제

2667번: 단지번호붙이기

---

풀이

# 1 - 집이 있는 곳, 0 - 집이 없는 곳
# 단지 수 출력, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력해라.

import sys
input = sys.stdin.readline

# 정사각형 지도 크기
n = int(input())

square_map = []

for i in range(n):
    square_map.append(list(map(int, input().rstrip())))

cnt = 0
result = 0

def dfs(x, y):
    global result
    # 탈출 조건 명시
    if x < 0 or y < 0 or x >= n or y >= n:
        return False
    
    # 집이 있는 곳 표시
    if square_map[x][y] == 1:
        # 방문 표시
        square_map[x][y] = 0
        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)
        result += 1
        return True 
    return False

house_list = []

for i in range(n):
    for j in range(n):
        if dfs(i, j) == True:
            cnt += 1
            house_list.append(result)
            result = 0


house_list.sort()

print(cnt)
for i in range(len(house_list)):
    print(house_list[i])

아이디어

• DFS 재귀로 풀었다. 현재 위치에서 상하좌우로 인접한 위치를 탐색하기 위해 dfs(x - 1, y), dfs(x + 1, y), dfs(x, y - 1), dfs(x, y + 1)를 재귀적으로 호출
• 현재 위치에 집이 있으면(square_map[x][y] == 1), (square_map[x][y] == 0)으로 방문처리 해준다.
• 현재 단지에 속한 집의 수를 result += 1로 세준다.
• 연결된 집을 모두 방문했다면 True를 반환해 현재 단지 탐색이 완료되었음을 표시한다. 이때 cnt +=1 을 해줘 총 단지수를 세준다.

✔️ 처음에 지도라고 변수명을 map으로 하면 파이썬 내장 함수 map()과 이름이 같아 'TypeError: 'list' object is not callable' 에러가 나므로 조심하자.