BaekJoon - 2667번: 단지번호붙이기 (그래프, 탐색)

SM 마에스트로 준비가 한창인 와중, DFS에 대해 자신감이 생겼다 싶어서 도전 해 본 문제이다

한 번에 맞춰 기분이 좋은 문제였다

---

문제

---

문제 분석

이 문제는 DFS를 이용해서 풀 수 있다.

재귀적인 방법을 통해 하나를 발견하면 상, 하, 좌, 우로 이동하며 재탐색을 하는 과정을 거친다

그리고 DFS 한 번 실행될 때마다 단지 하나가 1 -> 0으로 바뀌므로 그 타이밍에 count + 1 하는 방법을 생각했다

후에 한 DFS 사이클이 끝날 때마다 count를 초기화시키는 방법으로 단지 별 건물 수를 세었다

---

코드 작성

N = int(input())

house = []
for i in range(N):
    house.append(list(map(int, input())))
# 단지의 건물 개수를 담을 변수
count = 0


def dfs(x, y):
    # count를 글로벌 변수로 두고 사용
    # 범위 안에 있다면 상하좌우를 탐색해가며 단지 건물을 지워나감
    # 지워나가는 횟수를 count하고 아래에서 단지 별로 끊어서 내보낸다
    global count
    if x <= -1 or x >= N or y <= -1 or y >= N:
        return False
    if house[x][y] == 1:
        house[x][y] = 0
        count += 1
        dfs(x + 1, y)
        dfs(x - 1, y)
        dfs(x, y + 1)
        dfs(x, y - 1)
        return True
    return False

# 단지 별 건물 개수를 담을 배열, count가 들어간다
house_group = []
for i in range(N):
    for j in range(N):
        # dfs가 한 차례 실행되고 그동안 count된 횟수 = 단지 별 건물 수
        if dfs(i, j) == True:
            house_group.append(count)
            count = 0
# 단지 수를 출력하고 건물 개수를 오름차순으로 출력
house_group.sort()
print(len(house_group))
for i in range(len(house_group)):
    print(house_group[i])

---

실행 및 마무리

정상적으로 출력 되는 모습을 볼 수 있다!

---

End