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

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

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

---

접근 방법: DFS

• 그래프 탐색과 관련된 문제이므로 그래프 이론 중 하나인 DFS를 이용하여 풀어보기로 했다.

• 전체 그리드를 하나씩 순회하며 "1"값을 만나면 단지가 시작되는 지점이므로 그 좌표를 부모노드, 그 좌표의 상하좌우에 인접한 좌표를 자식노드로 삼는 그래프를 만들어 DFS 방식으로 탐색하였다.

재귀함수

import sys

global N
global GRID
global SIZE

N = int(sys.stdin.readline())
GRID = []
for _ in range(N):
    GRID.append(list(sys.stdin.readline().strip()))
SIZE = []

# recursion
def dfs(i, j):
    global N
    global SIZE
    global GRID

    if GRID[i][j] == "1":
        SIZE[-1] += 1
        GRID[i][j] = "0"
    else:
        return

    if i > 0: dfs(i-1, j)
    if j > 0: dfs(i, j-1)
    if i + 1 < N: dfs(i+1, j)
    if j + 1 < N: dfs(i, j+1)
    return
# end recursion

for i in range(N):
    for j in range(N):
        if GRID[i][j] == "1":
            SIZE.append(0)
            dfs(i, j)
            # 매 단지 탐색이 끝날때마다 그리드를 출력
            # print(*GRID, sep='\n')
            # print()

print(len(SIZE), *sorted(SIZE), sep='\n')

• 문제로부터 N, GRID 를 입력받아 변수에 저장한 뒤, 그리드의 좌표를 하나씩 순회하며 값이 "1"인 지점을 찾고, 이 부분이 단지의 시작이므로 SIZE 리스트에 0을 추가한 뒤 그 좌표를 dfs() 로 보내 재귀함수를 돌린다.

• 재귀함수 내부에서는 현재 좌표의 값을 참고해 "1"이라면 "0"으로 바꾼 뒤 단지의 사이즈를 1 늘리고 그리드를 벗어나지 않는 선에서 상하좌우의 좌표를 dfs() 에 넣어 재귀적으로 함수를 호출하게 했다.

• 만약 현재 좌표의 값이 "0"이라면 이미 탐색했던 좌표이거나, 혹은 단지에 포함되지 않는 공간이므로 바로 return 해주었다.

• 이렇게 한 단지의 탐색을 모두 끝마치면 단지가 있던 좌표들은 모두 "0"값으로 바뀌고, "1"이 "0"값으로 바뀔 때 마다 SIZE 의 값을 늘려주었으므로 단지의 크기도 구해진다.

• 마찬가지로 전체 그리드를 모두 탐색하면 SIZE 리스트에 각 단지의 크기가 입력된다. 전체 단지의 갯수는 len(SIZE) 로 구할 수 있으므로 문제가 요구하는 조건에 맞게 정렬하여 모두 출력해주면 된다.

스택

• DFS로 그래프를 탐색하는 방법에는 재귀함수 말고도 스택을 이용하는 방법이 있다.

• 전체적인 흐름은 똑같으나, 재귀적으로 호출하던 함수들의 매개변수값을 스택에 넣어주어 while문으로 스택이 모두 없어질 때 까지 반복시켜준다.

import sys

N = int(sys.stdin.readline())
GRID = []
for _ in range(N):
    GRID.append(list(sys.stdin.readline().strip()))
SIZE = []

# stack
stack = []
for i in range(N):
    for j in range(N):
        if GRID[i][j] == "1":
            stack.append([i, j])
            SIZE.append(0)
            while stack:
                x, y = stack.pop()
                if GRID[x][y] == "1":
                    SIZE[-1] += 1
                    GRID[x][y] = "0"
                else:
                    continue
                if x > 0: stack.append([x-1, y])
                if y > 0: stack.append([x, y-1])
                if x + 1 < N: stack.append([x+1, y])
                if y + 1 < N: stack.append([x, y+1])
            # 매 단지 탐색이 끝날때마다 그리드를 출력
            # print(*GRID, sep='\n')
            # print()
# end stack

print(len(SIZE), *sorted(SIZE), sep='\n')