[백준 알고리즘: python 3] #2667 - 단지번호 붙이기 (DFS 스터디)

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

 

2667번은 DFS/BFS 단계별 문제에 있는 정답률 약 38%의 문제입니다. 정답률에 비해 DFS의 개념을 잘 적용할 수만 있으면 그렇게 어렵지는 않은 문제였습니다.

 

DFS는 깊이 우선 탐색이라는 뜻의 Deep-First Search 의 줄임말입니다. 정점과 간선으로 이루어진 그래프에서 모든 정점을 방문하는 방법인데, 정확한 정의는 한 임의의 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 즉, 한 정점에서 간선을 따라 이동한다고 할 때, 이동한 정점에도 간선이 있을 경우 더이상 연결된 정점이 없을 때까지 계속해서 연결된 정점을 탐색합니다. 더 이상 다른 정점으로 연결된 간선이 없는 마지막 정점에 도착을 했을 경우, 탐색을 한 경로를 분기(Branch, 가지)라고 하는 것 같습니다. 그림을 통한 설명이 이 블로그에 잘 정리가 되어 있으니 들러보시길 바래요! 

 

Hint!

이 문제는 DFS의 개념을 크게 벗어나는 문제는 아니지만, 2차원 배열로 문제가 주어졌다는 점이 조금 다릅니다. 그래도, 간선이 연결되었음을 보여주는 지표는 "어떤 집의 상하좌우에 다른 집이 있으면 다른 단지로 본다." 이므로 이 점만 유의하면 되겠네요. 정점이 간선으로 연결되어 있음을 저 규칙으로 규정을 짓기만 하면 DFS는 그냥 개념대로 구현만 하면 됩니다.

 

DFS는 말로 설명듣는 것보다 저는 코드를 통해 설명하는게 나을 것 같더라구요. 그래서 아래 코드에 주석을 조금 자세히 남겨두었습니다. DFS 구현이 핵심이었으니, 자기 자신의 힘으로 풀고는 싶으나 구현이 머리아플 때 제 코드의 dfs 함수부분에 주석만 살짝 참고해보세요!

 

아래 코드로 성공하였습니다.

 

import sys

def dfs(x, y):
    global visited
    global base
    global amount
    global N

    if not base[x][y]: return False
    # 일단 방문한 집은 방문했다고 표시한다.
    visited[x][y] = True
    # 변을 공유하는 집끼리는 간선으로 연결되어 있다고 본다.
    adjacents = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
    
    for ax, ay in adjacents:
        # 변을 공유하는 집의 좌표가 범위 내에 있는 경우에
        if 0 <= ax < N and 0 <= ay < N:
            # 집이 있지만 방문하지 않은 정점이 있으면
            if base[ax][ay] and not visited[ax][ay]:
                # 단지의 크기를 1 늘리고
                amount += 1
                # 그 정점에 또 연결된 단지가 없는지 탐색(DFS)한다.
                dfs(ax, ay)
        
N = int(sys.stdin.readline())
visited = [[False for _ in range(N)] for _ in range(N)]
groups = []
base = []
for _ in range(N):
    base.append(list(map(int, sys.stdin.readline().replace("\n", ""))))

for x in range(N):
    for y in range(N):
        # x, y에 집이 있고 방문하지 않은 정점이라면
        if base[x][y] and not visited[x][y]:
            # 먼저 단지 크기를 1로 시작하고
            amount = 1
            # 그 집 주변에 인접한 집이 없는지 탐색한다.
            dfs(x, y)
            # 탐색이 끝나면 계산된 단지 크기를 답 목록에 넣는다.
            groups.append(amount)

print(len(groups))
groups.sort()
for i in groups:
    print(i)