[백준 알고리즘/Python] 2667 단지번호 붙이기

문제

 

 

문제 이해

dfs로 하나의 좌표가 1이라면 다른 1을 찾아서 쭉쭉 스택을 쌓는 형식으로 풀면 됩니다.

이번에는 dfs가 스택이 쌓일 때의 수와 1개의 사이클이 끝날 때를 고려했습니다.

 

import sys
sys.setrecursionlimit(10**6)

c = [] # dfs 한 사이클 돌 때 나오는 수
r = [] # 나오는 수를 오름차 순으로 
def dfs(x,y,count):

    #주어진 범위를 벗어나면 종료
    if(x <= -1 or x >= n or y <= -1 or y >= n):
        return False

    if(graph[x][y] == 0):
        return False

    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    if(graph[x][y] == 1):
        graph[x][y] = 0

        count += 1 #하나의 사이클의 호출 횟수 
        
        dfs(x-1,y,count)   # 상
        dfs(x,y-1,count)   #왼쪽
        dfs(x,y+1,count)   #오른쪽
        dfs(x+1,y,count)   #아래
        
        c.append(count)
    
        return True
    
n = int(input())

#2차원 배열 만들기
graph = []
for i in range(n):
    graph.append(list(map(int,input())))
result = 0

#정의된 DFS 함수 호출
for i in range(n):
    for j in range(n):
        if(dfs(i,j,0) == True): # 한 사이클이 끝남
            result += 1
            r.append(len(c))
            c.clear()

print(result)

r.sort()
for p in r:
    print(p)

만약 graph에서 1을 만다면 dfs의 재귀(스택) 호출이 되니깐 그 때 부터 1을 넣어줍니다. 처음에는 0입니다.

 

c 리스트는 dfs가 호출 될 때마다 리스트의 크기를 1씩 키웁니다. 

 

그리고 마지막에 호출되는 dfs함수는 r 리스트에다가 얼마나 dfs가 호출되었는지 담습니다. 이건 dfs 함수 밖에 있기 때문에 프로그램 어디서든 사용할 수 있습니다.  

 

한 사이클이 끝날 때마다 dfs가 얼마나 호출되었는지 보고 c 리스트를 초기화 해줍니다. 안그러면 이전의 단지들을 기억하고 있기 때문입니다.

호출 횟수(r리스트)를 오름차순으로 정렬하고 출력해줍니다.