[백준] 2667번 단지번호붙이기

 

 

이 문제 역시 그래프 탐색 문제입니다.

 

접근법

- DFS로 접근

- DFS로 탐색하면서 cnt를 증가하여 단지 내 건물 수 체크

- 건물 수 담은 리스트 활용하여 결과 출력

 

n = int(input())
matrix = []
visited = [[False] * n for _ in range(n)]
cnt_list = []
dx = [0,0,1,-1]
dy = [1,-1,0,0]

# mapping matrix
for _ in range(n):
    m = input()
    matrix.append(m)

def dfs(matrix,x,y,visited):
    global cnt
    if x < 0 or x >= n or y < 0 or y >= n :
        return 0
    if matrix[y][x] == "0" or visited[y][x] :
        return 0
    
    visited[y][x] = True
    cnt = 1
        
    for i in range(4):
        nx = x + dx[i] 
        ny = y + dy[i]
        cnt += dfs(matrix, nx,ny,visited)
    return cnt
        
for b in range(n):
    for a in range(n):
        if matrix[b][a] == "1" and not visited[b][a]:
            cnt = 0
            cnt_list.append(dfs(matrix, a,b, visited))
        
cnt_list.sort()
print(len(cnt_list))
for i in cnt_list:
    print(i)

 

 

그래프 탐색에 조금 더 익숙해진 느낌입니다. 

역시 문제를 많이 풀어보는게 중요한 것 같습니다.