[BOJ] 백준 2667 단지번호붙이기 / BFS, DFS

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

 

💭 풀이 과정

 

 

탐색 문제로서 BFS와 DFS 두 가지 방법 모두 가능한 문제이다.

 

N의 크기가 최대 25로 매우 작다.

그러므로 n²의 방법으로 모든 공간을 탐색하며 집이 있는 공간인 1을 발견하면 그 지점에서 탐색을 시작한다.

 

탐색을 마치고 구해진 크기(단지 크기)를 리스트에 append한다.

 

모든 연산이 마치면 리스트에는 단지들의 크기가 저장된다.

 

리스트의 길이가 단지 수가 되고,

리스트를 오름차순 정렬하여 원소들을 출력하는 것으로 마친다.

 

 

 

작성언어: Python

 

 

BFS

from sys import stdin
from collections import deque

n = int(stdin.readline().rstrip())
square = [list(map(int, list(stdin.readline().rstrip()))) for _ in range(n)]
queue = deque()
villages = []
# 좌 우 상 하
mx = [0, 0, -1, 1]
my = [-1, 1, 0, 0]

for i in range(n):
    for j in range(n):
        if square[i][j] == 1:
            # 탐색 중 1을 찾으면 거기서 bfs 시작
            queue.append((i, j))
            square[i][j] = 2  # 시작점 방문처리
            village_size = 1
            while queue:
                x, y = queue.popleft()

                for k in range(4):
                    nx = x + mx[k]
                    ny = y + my[k]
                    if 0 <= nx < n and 0 <= ny < n:
                        if square[nx][ny] == 1:
                            queue.append((nx, ny))
                            square[nx][ny] = 2  # 방문처리
                            village_size += 1

            villages.append(village_size)
print(len(villages))
villages.sort()
for size in villages:
    print(size)

 

 

DFS

from sys import stdin

n = int(stdin.readline().rstrip())
maps = [list(map(int, list(stdin.readline().rstrip()))) for _ in range(n)]
size = 0


def dfs(x, y):
    # 상 하 좌 우
    mx = [-1, 1, 0, 0]
    my = [0, 0, -1, 1]
    global size, maps, n
    maps[x][y] = 2    # 방문처리
    size += 1
    for k in range(4):
        nx = x + mx[k]
        ny = y + my[k]
        if 0 <= nx < n and 0 <= ny < n:
            if maps[nx][ny] == 1:
                dfs(nx, ny)


if __name__ == "__main__":
    villages = []
    for i in range(n):
        for j in range(n):
            if maps[i][j] == 1:
                dfs(i, j)
                villages.append(size)
                size = 0

    villages.sort()
    print(len(villages))
    for num in villages:
        print(num)