[ 백준 ] 2667번 : 단지번호 붙이기 (파이썬 / DFS)

문제 )

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

2667번: 단지번호붙이기

 

[ 풀이 ]

아파트들을 모두 순회해야함으로 탐색 알고리즘 DFS를 사용하여 문제를 풀어보았다.

우선, 입력받은 값들 (집의 위치)을 home list에 저장하였고 방문한 집을 표시하는 visit list도 만들어주었다. 

또한, 방향을 알려주는 list인 dx와 dy를 이용하여 문제를 풀어주었다. 
현재 집을 기준으로 오른쪽,왼쪽,위,아래에 있는 집들을 접근하기 위한 list이다.

	x좌표 (dx)	y좌표 (dy)
(1) Right	+1	0
(2) Left	-1	0
(3) Top	0	+1
(4) Bottom	0	-1

 

< Post Function의 Algorithm >

✔ 단지의 수를 세는 변수 → count
✔ 1개 단지의 집의 수를 세는 변수 → num
✔ 각 단지의 총 집의 수 저장 → countlist

1. 모든 집을 방문 (N*N개) 
2. 집이 있지만 방문하지는 않은 경우
             Ⅰ. dfs fuction 수행 (1개 단지의 집의 수 세는 Function )
             Ⅱ. countlist에 단지의 집의 수 저장
             Ⅲ. num을  1로 초기화
             Ⅳ. count에 1 더해준다. ( 1개의 단지가 끝났기 때문 )

 

< dfs Function의 Algorithm >

✔ 방향을 알려주는 list → dx, dy
✔ 단지의 수를 세는 변수 → count
✔ 1개 단지의 집의 수를 세는 변수 → num (initailize 1)
✔ 집의 x좌표, y좌표 → i, j

1. 집을 방문 했으므로 visit[i][j]=1
2. 현재 집을 기준으로 4방면의 집들 확인 ( Left → Right → Top → Bottom )
           Ⅰ. 이웃 집의 x좌표, y좌표 구하기 → 방향 + 현재좌표
           Ⅱ. 이웃 집의 x,y좌표가 N보다 작은 경우
          Ⅲ . 이웃을 방문하지 않았고 이웃이 존재하는 경우
                                   (1) num에 1을 더해준다 ( 이웃이 존재하기 때문 )
                                   (2) dfs function수행 (이웃 집에 대해)                            

 

- python code 

from sys import stdin

# 방향을 알려주는 list -> left,right,top,bottom
dx=[-1,1,0,0]
dy=[0,0,1,-1]

num=1  # 1개 단지의 집의 수
def dfs(i,j):
    global count,num
    visit[i][j]=1 # 방문 했으므로 1로 만들어줌

    # 현재 집을 기준으로 4방면의 집들 확인 ( Left → Right → Top → Bottom )
    for k in range(4):
        # 이웃 집의 x좌표, y좌표 구하기 → 방향 + 현재좌표
        x=i+dx[k]
        y=j+dy[k]
        if 0<=x<N and 0<=y<N:
            # 이웃을 방문하지 않았고 이웃이 존재하는 경우
            if visit[x][y]==0 and home[x][y]==1:
                num+=1
                dfs(x,y) # 이웃 집에 대해 dfs 수행   


def post():
    global count,num,countlist
    for i in range(N):
        for j in range(N):
            # 집이 있지만 방문하지는 않은 경우
            if home[i][j]==1 and visit[i][j]==0:
                dfs(i,j)
                countlist.append(num)
                num=1
                count+=1 # 1개의 단지가 끝났기 때문


N=int(input())
home=[[0]*(N)for i in range(N)]
visit=[[0]*(N)for i in range(N)]


count=0 # 단지 수
countlist=[] # 각 단지 별 총 집의 수
for i in range(N):
    l=stdin.readline().strip()
    for j,v in enumerate(l):
        home[i][j]=int(v)
    

post()
print(count)
for i in sorted(countlist):
    print(i)