[파이썬] 2667번 '단지번호붙이기' 문제 풀이

[파이썬] 2667번 '단지번호붙이기' 문제 풀이

현재의 위치에서 상하좌우를 확인하며 방문처리를 하고 그 이후 다시 반복문을 돌면서 방문처리가 되지 않은 노드가 있다면 다시 dfs를 진행하여 방문 처리를 합니다.

(풀이에서는 한번 방문한 곳은 방문하지 못하게 집이 있는 곳 1을 집이 없는 곳인 0으로 변환.)

이때 방문처리의 횟수가 각각의 단지 내의 집의 개수가 됩니다.

NHN그룹의 1차 pre-test문제와 같은 유형의 문제

https://lbdiaryl.tistory.com/171?category=1028082

풀이

def dfs(x,y): if x<=-1 or x>=n or y<=-1 or y>=n: pass else: if Mat[x][y] == 1: Mat[x][y] = 0 List[Count]+=1 dfs(x - 1, y) dfs(x, y - 1) dfs(x + 1, y) dfs(x, y + 1) n=int(input()) Mat=[(list(map(int,list(input())))) for _ in range(n)] List=[] Count=0 for i in range(n): for j in range(n): if Mat[i][j]==1: List.append(0) dfs(i,j) Count+=1 List.sort() print(len(List)) for i in List: print(i)

from http://lbdiaryl.tistory.com/188 by ccl(A) rewrite - 2021-10-22 20:01:16