백준 2667

 

DFS로 구현하려고 하니,

n = int(input())
graph = []
for i in range(n):
  graph.append(list(map(int, input())))

print(graph)

def dfs(x, y):
  if x <= -1 or y <= -1 or x >= n or y >= n:
    return False
  if graph[x][y] == 1:
    graph[x][y] == 0
    dfs(x - 1, y)
    dfs(x, y - 1)
    dfs(x + 1, y)
    dfs(x, y + 1)
    return True
  return False

result = 0
for i in range(n):
  for j in range(n):
    if dfs(i, j) == True:
      result += 1

print(result)

 

 

RecursionError가 뜬다.

 

BFS로 구현한 코드

from collections import deque

n = int(input())
map_data = [list(map(int, input())) for _ in range(n)]
visited = [[False]*n for _ in range(n)]  # 방문 여부를 저장하는 2차원 리스트

dx = [-1, 0, 1, 0]  # 이동할 네 방향 (상, 우, 하, 좌)
dy = [0, 1, 0, -1]

def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = True
    count = 1  # 현재 단지에 속한 집의 수
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if not visited[nx][ny] and map_data[nx][ny] == 1:
                queue.append((nx, ny))
                visited[nx][ny] = True
                count += 1
    return count

counts = []  # 각 단지에 속한 집의 수를 저장하는 리스트
for i in range(n):
    for j in range(n):
        if map_data[i][j] == 1 and not visited[i][j]:
            counts.append(bfs(i, j))

counts.sort()  # 각 단지에 속한 집의 수를 오름차순으로 정렬

print(len(counts))  # 총 단지수 출력
for count in counts:
    print(count)  # 각 단지에 속한 집의 수 출력