[백준] 2667. 단지번호붙이기 (DFS/Python)

-풀이

n = int(input())
map_n = []

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

for i in range(n):
    map_n.append(list(input()))

dan = 0
con_list = []

for i in range(n):
    for j in range(n):
        if map_n[i][j] == '1' :
            dan += 1
            stack = [(i, j)]
            map_n[i][j] = 0
            count = 1
            while stack :
                a, b = stack.pop()
                for k in range(4):
                    to_x = a + dx[k]
                    to_y = b + dy[k]
                    if to_x >= 0 and to_y >= 0 and to_x < n and to_y < n :
                        if map_n[to_x][to_y] == '1':
                            stack.append((to_x, to_y))
                            map_n[to_x][to_y] = 0
                            count +=1
            con_list.append(count)

print(dan)
for i in sorted(con_list):
    print(i)

visited 함수를 만드는 대신 0으로 바꿔주었다.

​

# 로직

1. 전체맵 완전탐색

2. 집이 있으면 단지 수 증가

3. stack에 해당 위치의 index 추가한 뒤 값을 0으로 변경 (visited 를 따로 만드는 대신 한 번 확인한 곳은 다시 확인하지 않도록 하기 위해)

4. while문을 돌며 상하좌우를 탐색하며 인접한 위치에 집이 있다면 index를 stack에 추가하고 해당 값을 0 으로 변경, count 증가 (집 개수 세기)

​