[Python] 🥈백준 2667 단지 번호붙이기 /DFS를 활용하여 연결요소 구하기

예제 입력 1

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력 1

3
7
8
9

 

 

아이디어 생각하기

 

연결요소 문제는 풀어도 풀어도 뇌리에 안 박혀서 이렇게 블로그를 쓰고자 한다.... 

 

 

 

로직순서

변수설명

map: 지도, home:  각각 단지내 집의 수, nums:  각각 단지내 집의 수를 담는 리스트

(1) 단지 지도 생성

(2) dfs 알고리즘을 돌며,  ⓐ 범위를 벗어날 때 ⓑ집이 있을 때 ⓒ집이 없을 때 경우를 나눈다.  ⓐ ⓒ는 return False

(3) ⓑ 집이 있을 때의 경우,

home +=1

집을 1개 추가하고

maps[x][y] = 0 #숫자를 세고 0으로 집을 없앰

다시 못 돌게 집을 없애버린다

dfs(x-1,y) #상하좌우 재귀
dfs(x,y-1)
dfs(x+1,y)
dfs(x,y+1)

상하좌우를 재귀하며 주위에 집이 있는지를 확인하고, 주위에 집이 있을 경우 return True 이는 단지가 있다는 뜻이다.

(4) 이중 for문으로 가로, 세로를 정사각형 지도의 요소를 돈다 [0][0]~[n][n]을 탐색한다.

만약 def(i,j)가 True일 경우, (단지가 있을 경우)

nums.append(home)

하여 리스트에 집의 개수를 넣고, 다음 단지도 돌아야하므로 home = 0으로 초기화한다. 

 

 

(4) nums를 sort하여 오름차순하고, for문을 돌며 하나씩 출력한다.

 

 

 

정답코드

#단지 출력하기 dfs
import sys
sys.stdin.readline
sys.setrecursionlimit(10**8) #재귀함수 limit
input = sys.stdin.readline

n = int(input())

#단지 지도 만들기
maps = []
for i in range(n):
    maps.append(list(map(int, input().strip())))

home = 0#한 단지에 집이 몇개인지 셀 변수
def dfs(x,y):
    global home 
    if x < 0 or y < 0 or x >= n or y >= n: #범위를 벗어나면 fasle
        return False
    if maps[x][y] == 1:#만약 집이 있으면
        home += 1 #집의 수 1개 추가
        maps[x][y] = 0 #숫자를 세고 0으로 집을 없앰
        dfs(x-1,y) #상하좌우 재귀
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True #True 반환
    return False :#집이 없을 경우 (0일 경우) false

nums = [] # 각 단지의 집의 수를 담는 리스트
for i in range(n):
    for j in range(n):
        if dfs(i,j) == True:
            nums.append(home) #리스트에 집의 수 출력
            home = 0 #한 단지에 있는 집의 수를 다시 0으로 초기화
nums.sort() #오름차순
#내림차순은 nums = sorted(nums, key= lambda -x:0)

print(len(nums)) #몇단지까지 있는지 출력
for i in nums:
  print(i) #단지마다의 집의 개수 출력