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

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

2667번: 단지번호붙이기

문제 요약 : 

<그림1>같이 단지가 주어졌을 때, <그림 2>같이 단지를 구분할 수 있다. 총 단지의 수와 각 단지에 속하는 집의 수를 오름차순으로 출력하라.

 

풀이 ) 

DFS, BFS 둘다 풀 수 있는 문제

나는 DFS 재귀로 풀었다.

 

입력으로 받아온 apart를 for문으로 돌려서 0보다 크면 DFS가 돌아가도록 한다.

tmp값은 각 단지의 아파트 개수를 저장하기 위해 임의로 만든 값이고, 함수안에서도 계산될 수 있도록 global로 선언해주었다. DFS가 다 돌고 나면 tmp값을 ans 리스트에 추가 해주고 1로 초기화해준다.

 

DFS 함수 :

먼저 apart[x][y] 값을 0으로 변경하여 방문한 것을 구분할 수 있게 한다.

x,y값을 받아와 (x,y)를 기준으로 아래 위 오른쪽 왼쪽이 되는 좌표값(ix,iy)를 구한다.

ix와 iy가 범위(0=<ix,iy<N) 안에 있고 아직 방문하지 않았다면 DFS를 돌려준다.

 

마지막으로 단지의 개수와 각각의 아파트수를 정렬하여 출력한다.

N = int(input())
apart = [list(map(int,input())) for _ in range(N)]
ans = []
dx = [0,0,-1,1]
dy = [-1,1,0,0]
tmp = 1

def dfs(x,y):
    global tmp
    apart[x][y] = 0    # 지나간 거 체크
    
    for i in range(4):
        ix = x + dx[i]
        iy = y + dy[i]

        if 0 <= ix < N and 0 <= iy < N :
            if apart[ix][iy] > 0:
                tmp += 1
                dfs(ix,iy)

for x in range(N):
    for y in range(N):
        if apart[x][y] > 0 :
            dfs(x,y)
            ans.append(tmp)
            tmp = 1
            
print(len(ans))
ans.sort()
print(*ans, sep='\n')