문제
문제 이해
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리스트)를 오름차순으로 정렬하고 출력해줍니다.
728x90
'알고리즘 > 백준알고리즘' 카테고리의 다른 글
[백준 알고리즘/Python] 2178 미로 탐색 (0) | 2022.02.24 |
---|---|
[백준 알고리즘/Python] 4963 섬의 개수 (0) | 2022.02.22 |
[백준 알고리즘/Python] 11724 연결 요소의 개수 (0) | 2022.02.21 |
[백준 알고리즘/Python] 1260 DFS와 BFS (0) | 2022.02.19 |
[백준 알고리즘/Python] 1748 수 이어 쓰기1 (0) | 2022.02.18 |