백준 2667번 단지 번호 붙이기 파이썬 DFS

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

2667번: 단지번호붙이기

 

답안 

lst = []
n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
    
def dfs(x, y):
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False
    
    if graph[x][y] == 1:
        graph[x][y] = 0
        lst.append(0)
        dfs(x-1, y) # 상
        dfs(x, y-1) # 좌
        dfs(x+1, y) # 하
        dfs(x, y+1) # 우
        return True
    return False
    
result = 0
result_cnt = []
for i in range(n):
    for j in range(n):
        if dfs(i,j) == True:
            result += 1
            result_cnt.append(len(lst))
            lst = []
            
print(result)
result_cnt.sort()
[print(i) for i in result_cnt]

 

---

 

코드 설명

• lst를 선언 한 이유 : 

  각 블록의 개수를 세려고 만들었다.

 

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

  2차원 배열을 리스트로 이용해서 표현을 해보았다.

 

• def dfs(x, y):
      if x <= -1 or x >= n or y <= -1 or y >= n:# 좌표 이탈시 탐색 종료
          return False
      
      if graph[x][y] == 1:
          graph[x][y] = 0
          lst.append(0)  # 1에서 0으로 변환할때 리스트에 넣어 개수 세기
          dfs(x-1, y) # 상
          dfs(x, y-1) # 좌
          dfs(x+1, y) # 하
          dfs(x, y+1) # 우
          return True
      return False

      일단 좌표 이탈시 바로 함수가 끝나는 코드를 짰고,

      DFS 함수 안에서 탐색 하다가 1에서 0으로 바뀌는 순간, 개수를 어떻게 셀지 고민을 했다.

      결국 리스트에 아무 숫자(0)을 넣어 그 리스트의 크기를 세주는 코드를 짰다.

      처음엔 전역변수로 cnt를 선언했지만 재귀 함수를 이용해서 그런지 해결하지 못했다.  

 

• result = 0
  result_cnt = []
  for i in range(n):
      for j in range(n):
          if dfs(i,j) == True:
              result += 1
              result_cnt.append(len(lst))
              lst = []​

      연결된 집의 모임인 단지를 세기 위해 result 변수 선언을 했다.

      dfs 함수가 끝나 True로 될 시 단지 수를 하나씩 카운트하였고,

      또한 각각의 단지들이 몇 개씩 뭉쳐있는지 세어 result_cnt에 하나씩 넣어 주었다.

 

• print(result)
  
  result_cnt.sort() # 정렬
  [print(i) for i in result_cnt]

      마지막에 결과값을 출력하고,

      각각 단지가 몇 개씩 있는지 result_cnt에 넣은 것을 정렬까지 해주었다.

      그 다음 리스트 comprehension 을 통해 출력을 해주는 거까지 하여 코드를 완성 시켰다.