[백준/Python] DFS/BFS - 2667번 단지번호 붙이기

👩🏻‍🏫 DFS 풀이

##### 실행 순서 1
import sys
# 재귀 limit 설정
sys.setrecursionlimit(10000)

# 지도의 크기
n = int(sys.stdin.readline())

# 지도
graph = [[] for i in range(n)]
for i in range(n):
  graph[i] = list(map(int,sys.stdin.readline().rstrip()))
 
# 총 단지수
apt = []
# 상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

### 실행 순서 3
def dfs(x,y):
  global cnt
  # 방문 처리
  graph[x][y] = 0
  # 단지 내 집의 수 증가
  cnt += 1
  
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < n and 0 <= ny < n:
      if graph[nx][ny] == 1:
        dfs(nx,ny)
        
### 실행 순서 2: 입력 받고 입력 받은 값들로 for문을 돈다.
# garph[0][0] ~ graph[n][n]     
for i in range(n):
  for j in range(n):
    if graph[i][j] == 1:
      # 각 단지 내 집의 수
      cnt = 0
      dfs(i, j)
      # 단지 내 집의 갯수 다 세고 나와서, 단지 갯수 추가
      apt.append(cnt)

# 총 단지 수 출력
print(len(apt))
# 단지 정렬
apt.sort()
# 단지 갯수 출력
for i in apt:
  print(i)

👩🏻‍🏫 BFS 풀이

import sys
from collections import deque

# 지도의 크기
n = int(sys.stdin.readline())

# 지도
graph = [sys.stdin.readline() for _ in range(n)]

visited = [[False]*n for _ in range(n)]
# 총 단지수
apt = []

# BFS 구현
def bfs(x,y):
  # 입력받은 지도 '0'이거나 이미 방문한 곳이라면 return으로 빠져나온다.
  if graph[x][y]=='0' or visited[x][y]: 
    return
  # 상하좌우
  dx = [0,0,-1,1]
  dy = [-1,1,0,0]
  q = deque([(x,y)])
  visited[x][y] = True
  cnt = 0
  while q:
    x,y = q.popleft()
    # 단지 갯수는 여기서 세어준다.
    cnt += 1
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < n and 0 <= ny < n:
        if graph[nx][ny] == '1' and not visited[nx][ny]:
          q.append([nx,ny])
          visited[nx][ny] = True
  apt.append(cnt)

for i in range(n):
  for j in range(n):
    bfs(i,j)

# 총 단지 수 출력
print(len(apt))
# 정렬해서 출력
for i in sorted(apt):
  print(i)

✏️ Python 문법

global

• 함수 안에서 전역 변수의 값을 변경하려면 global 키워드를 사용해야 함

x = 10
def foo():
	global x     # 전역변수 x를 사용하겠다
    x = 20       # 전역변수 x 값 변경
    print(x)     # 20
    
foo()
print(x)         # 20