Algorithm: DFS(Depth First Search)

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

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

global 변수 사용

import sys
sys.setrecursionlimit(10**6)

n = int(input().strip())
# '0110100' 같은 한 줄을 -> ['0','1','1'...]-> [0,1,1,...]로 변환
graph = [list(map(int, input().strip())) for _ in range(n)]
num = []          # 각 단지 크기 모음
count = 0         # 현재 단지 크기(DFS로 누적)

# 4방향(좌, 우, 상, 하) — 문제 조건에서 대각선은 제외
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y):
    """(x,y)에서 시작해 연결된 집(1)을 모두 0으로 바꾸며 count 증가."""
    global count
    # 경계 밖이면 종료
    if x < 0 or x >= n or y < 0 or y >= n:
        return False
    # 집이 있는 칸(1)이라면 방문 처리(0으로 바꾸기) + 카운트 증가
    if graph[x][y] == 1:
        count += 1
        graph[x][y] = 0
        # 인접 4방향으로 계속 확장
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            dfs(nx, ny)
        return True  # 시작점에서 True를 반환해서 “새 단지 발견” 신호로 사용
    return False     # 집이 없으면 단지 시작점이 아님

result = 0  # 단지 수
for i in range(n):
    for j in range(n):
        # dfs가 True == (i,j)에서 새 단지를 시작했다는 뜻
        if dfs(i, j):
            num.append(count)  # 방금 완성된 단지 크기 기록
            result += 1
            count = 0          # 다음 단지 카운트를 위해 리셋

num.sort()
print(result)
print(*num, sep="\n")

dfs가 크기를 반환

import sys
sys.setrecursionlimit(10**6)

n = int(input().strip())
graph = [list(map(int, input().strip())) for _ in range(n)]
num = []

# 상하좌우
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def dfs(x, y):
    # 범위 밖
    if x < 0 or x >= n or y < 0 or y >= n:
        return 0
    # 집이 없으면 종료
    if graph[x][y] == 0:
        return 0

    # 방문 처리(지우기)
    graph[x][y] = 0
    size = 1
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        size += dfs(nx, ny)
    return size

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            num.append(dfs(i, j))

num.sort()
print(len(num))
print(*num, sep="\n")

2. [프로그래머스] 네트워크

https://school.programmers.co.kr/learn/courses/30/lessons/43162

지도 기반 탐색

상하좌우(dx, dy)는 "지도" 기반 탐색

def solution(n, computers):
    #A->B, B->C => A->C
    #computer[i][i] = 1

    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    network = []
    
    def dfs(x, y):
        if x < 0 or x >= n or y < 0 or y >= n:
            return 0
        
        if computers[x][y] == 0:
            return 0
        
        computers[x][y] = 0
        size = 1
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            size += dfs(nx, ny)
            
        return size

    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1:
                network.append(dfs(i, j))

    return len(network)

그래프 기반 탐색

연결된 노드 DFS는 "그래프" 기반 탐색 -> 여기서는 이 방법이 적절

def soluction(n, computers):
	visited = [False] * n
    networks = []
    
    def dfs(node):
    	visited[node] = True
        size = 1
        for next_node in range(n):
        	if computers[node][next_node] == 1 and not visited[next_node]:
            size += dfs(next_node)
        return size
    for i in range(n):
    	if not visited[i]
        	size = dfs(i)
            networks.append(size)
            
	return len(networks)