백준 2667번 단지번호붙이기 _ DFS (python)

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

2667번: 단지번호붙이기

백준 1260번 단지 번호 붙이기

이번에 풀어볼 문제는 바로 이전 포스팅에서 구현했던 DFS와 BFS문제를 활용하는 문제입니다.
그 중 DFS를 활용하는 대표적인 문제인데요. 혹시 DFS나 BFS처럼 트리탐색 자체의 구현이 궁금하신 분들은 이전 포스팅을 참고해주세요.
2020/03/15 - [Programming/백준 문제풀이] - 백준 1260번 DFS와 BFS (python 구현)

백준 1260번 DFS와 BFS (python 구현)

이번 문제를 DFS를 활용하여 푼 이유는 딱히 없어요..
사실 이런 문제는 BFS든, DFS든 어떤 방법을 이용해서든 2차원 배열을 순회하며 탐색할 수 있는지를 물어보는 문제랍니다.

이 문제에서는 각각의 칸들이 Vertex로 Node가 되구요,
단지란, 상하좌우의 방향으로 1-1 끼리 Edge들이 연결되어 있는 트리라고 생각을 하는 게 가장 우선이랍니다.

추가적으로 제일 왼쪽 노드에서는 왼쪽으로 Edge를 연결할 수 없고, 제일 위쪽 노드에서는 위쪽으로 Edge를 연결할 수 없겠죠?
그렇게 노드를 연결할 수 없는 쪽은 따로 예외처리를 해주어야 하구요.

그리고 Edge가 연결되어있지 않는 경우에는 서로 다른 트리, 즉 코드내에서 서로 다른 단지들을 따로 카운트 하는 위치와,
단지 내의 집 수를 카운트하는 위치가 또 다른 체크포인트가 되겠네요.

그럼 바로 코드를 확인해볼까요?

size = int(input())
address = [] // 집의 유무 (1,0)을 저장
visited = [[0 for _ in range(size)] for _ in range(size)] // 방문 기록 저장
answer =[] //  단지 내 집 수 저장
counter = 0 // 단지 갯수 저장

for i in range(size):
    address.append(list(map(int, input())))

def DFS(row,col):
    if (visited[row][col] == 0): // 만약 집이 방문된 적 없다면
        visited[row][col] += 1 // 방문기록 추가
        if (address[row][col] == 1): // 만약 집이 존재한다면 (1)
            answer[counter] +=1 // 현재 단지 번호에 해당하는 집 수 1 증가
            if (row>0): // 왼쪽 이동 가능여부
                if (visited[row-1][col]==0):
                    DFS(row-1,col)     
            if (col>0): // 위쪽 이동 가능 여부
                if (visited[row][col-1]==0):
                    DFS(row,col-1)
            if (row<size-1): // 우측 이동 가능 여부
                if (visited[row+1][col]==0):
                    DFS(row+1,col)     
            if (col<size-1): // 아래쪽 이동 가능 여부
                if (visited[row][col+1]==0):
                    DFS(row,col+1)

for i in range(size): 
    for j in range(size): // 모든 집을 순회하면서 
        if (visited[i][j] == 0 and address[i][j] == 1): // 집을 방문한 적 없고, 집이 존재한다면
            answer.append(0) // 단지 내 집 수
            counter += 1 // 단지 수
        DFS(i,j) // 깊이 우선탐색

print(counter+1)
answer.sort() // 정렬
for i in range(len(answer)):
    print(answer[i])

 

끝.