[백준] 2667번 단지번호붙이기 DFS - Python3

문제와 입력, 출력

예시 결과

시간 복잡도와 공간 복잡도

한 변의 길이가 최대 25인 정사각형이 주어졌으므로 최악의 시간 복잡도는 O(625)였다. 기본 연산이 1000번을 넘어가지 않기 때문에 이 문제는 DFS 재귀 알고리즘을 쓸 수 있겠다고 생각했다.

 

---

알고리즘과 코드

시간 복잡도를 분석했을 때 언급한 것처럼 이 문제를 DFS 재귀 알고리즘으로 풀기로 했다. 자연어 알고리즘은 다음과 같다.

 

1. 그래프를 생성한다.

2. 모든 좌표 각각을 시작 지점으로 삼아 DFS 재귀 알고리즘을 호출한다.

3. DFS 탐색을 시작한다.

 

• 좌표가 범위 밖이면
  • return False로 즉각 종료
• 집이 있으면(1)
  • 방문한 집의 수(cnt)를 1 증가시킨다
  • 방문한 집이 재방문 되는 것을 막기 위해 값을 0으로 재할당
  • 상,하,좌,우에 대해 DFS를 호출하고 끝에 도달하면 return True로 종료한다.
• 집이 없으면(0)
  • return False로 종료한다.

4. DFS 탐색의 return 값이 True라면 단지 수(result)를 1 증가시키고, 단지 내 집의 수(cnt)를 ans 리스트에 append 한다.

5. 다음 좌표에 대해서 2~4번을 수행한다.(dfs 탐색 전에 cnt = 0 으로 초기화한다.)

 

from collections import deque
import sys

input = sys.stdin.readline
n = int(input())

# 그래프 생성
graph = []
for i in range(n):
    graph.append(list(map(int,input().rstrip())))

# 탐색
def dfs(x,y):
	# 단지 내 집의 수
    global cnt
	
    # 지도 범위 밖이면 return False로 종료
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False
    
    # 집이 있는 경우(1)
    if graph[x][y] == 1:
        cnt += 1 # 단지 내 집의 수 + 1
        graph[x][y] = 0 # 방문 처리
        dfs(x-1,y) # 상
        dfs(x,y-1) # 좌
        dfs(x+1,y) # 하
        dfs(x,y+1) # 우
        return True
    
    # 집이 없는 경우(0)에는 return False
    return False

result = 0 # 단지의 수
ans = [] # 인덱스 i+1은 각각의 단지를 의미하고, 그 인덱스의 요소 값은 단지 내 집의 수를 의미

# 지도 안에 있는 모든 좌표 각각을 시작 지점으로 설정하여 dfs 탐색을 시도
for i in range(n):
    for j in range(n):
        cnt = 0 # 사전에, 단지 내 집의 수를 0으로 초기화
        if dfs(i,j) == True: # 단지가 발견 됨
            result += 1 # 단지 수 + 1
            ans.append(cnt) # 단지 수를 리스트 ans에 추가

print(result)
[print(i) for i in sorted(ans)] # ans를 오름차순으로 정렬 후 출력

 

---

세줄 요약

1. 최악의 시간 복잡도가 1000번 미만의 기본 연산인 경우 DFS 탐색도 해볼만 하다.

2. 미로 찾기 같은 문제의 분류는 DFS,BFS 모두 상,하,좌,우에 대한 탐색 필요

3.  미로 찾기 같은 문제의 분류는 DFS,BFS 모두 방문 처리 필요

---