단지번호붙이기 - 2667 (DFS & BFS)

 

def dfs(x,y):
  if x>= n or x<=-1 or y>=n or y<=-1: #벽에 부딪히면 종료
    return False

  if graph[x][y] == 1:#아파트 단지경우
    global cnt
    cnt+=1
    graph[x][y]=0 #방문처리
    dfs(x-1,y)#아래
    dfs(x+1,y)#위
    dfs(x,y-1)#왼
    dfs(x,y+1)#오
    return True
  return False

n = int(input())

#아파트 단지 정보 받기
graph = []
for i in range(n):
  graph.append(list(map(int,input())))

result = 0
cnt = 0
answer=[]
for i in range(n):
  for j in range(n):
    if dfs(i,j) == True:
      result+=1
      answer.append(cnt)
      cnt=0

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

기존의 음료수 얼려먹기 DFS문제에서 아주 살짝 수정했다.

살짝만 수정하는데도 시간이 조금 걸렸다.

아파트 단지일 경우에만 dfs()가 True를 반환할 수 있으니 아파트 단지일 경우에 cnt의 값을 1씩 증가시켜 세대수를 저장하고 재귀 함수를 끝마치면 answer에 cnt값을 넣어준 후 다시 0으로 초기화했다.

dfs()에서 값이 1일 때만 재귀 함수를 타는 이유는 아파트 단지가 될 수 있는지 알아보기 위함이다. 아파트가 있어야 동서남북으로 찾아보는 의미가 있으니 이점을 생각하면 많이 어렵진 않은 문제 같다.

 

from collections import deque

def bfs(x,y):
  dx = [-1,1,0,0]
  dy = [0,0,-1,1]
  
  queue = deque()
  queue.append((x,y))
  visit[x][y] = True
  
  cnt = 1
  while queue:
    x,y = queue.popleft()
    for i in range(4):
      nx = x+dx[i]
      ny = y+dy[i]
      if 0<=nx<n and 0<=ny<n and graph[nx][ny] == 1 and not visit[nx][ny]:
        graph[nx][ny] +=1
      
        queue.append((nx,ny))
        cnt+=1
  result.append(cnt)   
  
n = int(input())
graph = [list(map(int,input())) for _ in range(n)]
result=[]
visit = [[0]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    if not visit[i][j] and graph[i][j] == 1:
      bfs(i,j)


result.sort()
print(len(result))
for i in result:
  print(i)