백준 2667번 : 단지 번호

1. BFS로 풀었을 때

# 문제 : https://www.acmicpc.net/problem/2667
# 백준 2667번 : 단지번호
from collections import deque

num = int(input())
# 스페이스바 없이 출력 : https://lifeignite.tistory.com/51
graph = [list(map(int, input())) for _ in range(num)]  # map 객체의 index에 접근하려먼 list형으로 캐스팅해줘야 한다!

# 좌표 값 설정
dx = [0,0,1,-1]
dy = [-1,1,0,0]

# 단지 수
house_num = 0
# 단지 수 배열
house_array = []

# BFS : 1이 있을 때 그와 인접한 노드들을 방문 (1이 없을 때 까지), 방문한 경우 0으로 변경 (중복 X)
def BFS(graph,x,y):
  queue = deque()
  count = 1
  queue.append((x,y))
  graph[x][y] = 0

  while queue:
    n = len(graph)
    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 graph[nx][ny] == 1:
        graph[nx][ny] = 0
        count += 1
        queue.append((nx,ny))
  return count

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

house_array.sort()
print(len(house_array))
for i in range(len(house_array)):
  print(house_array[i])

• BFS 풀이의 경우 필요한 개념 : Queue 자료구조
• 하나의 마을을 탐색하는 데 있어서 인접한 모든 구역을 탐색하기 때문에 인접 구역이 1인 경우 모두 Queue에 삽입

2. DFS로 풀었을 때

# 문제 : https://www.acmicpc.net/problem/2667
# 백준 2667번 : 단지번호
num = int(input())
graph = [list(map(int, input())) for _ in range(num)] 

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

def DFS(x,y):
  global count
  if x < 0 or x >= num or y < 0 or y >= num:
    return False
    
  if graph[x][y] == 1:
    count += 1
    graph[x][y] = 0
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      DFS(nx,ny)
    return True
  return False

count = 0 # count 선언 , 없을 시 NameError 뜸

for i in range(len(graph)):
  for j in range(len(graph)):
    if DFS(i,j) == True:
      house_array.append(count)
      count = 0
  
house_array.sort()
print(len(house_array))
for i in range(len(house_array)):
  print(house_array[i])

• DFS 풀이의 경우 필요한 개념 : 재귀
• DFS 함수가 재귀이므로 반드시 탈출 조건이 있어야 한다
• count가 DFS 내에서 계속 값을 유지해야 하므로 전역변수인 global로 선언해야 한다.
  (지역변수의 경우 함수가 끝났을 때 변수가 사라지기 때문)
• DFS 함수 내에 count 선언이 있더라도 DFS 함수를 실행하기 전에 count 값을 생성해야 한다(count = 0)

실행속도는 DFS : 72ms, BFS : 92ms로 DFS가 더 빨랐다.

아무래도 코드 길이에 있어서도 재귀 함수를 사용하는 것이 더 간결하고,

collections 모듈을 사용하지 않기 때문인 것 같다.

하지만 난이도면에서 재귀 함수를 사용하여 구현하는 것이 좀 더 어려웠고,

직관적으로 접근했을 때 BFS를 사용하는 것이 더 알맞다고 생각했다.