[python] Level2_장애물 인식 프로그램

https://softeer.ai/practice/info.do?idx=1&eid=409 

Softeer

 

import sys
 
# 정사각형 n개 갯수받기
#sys.stdin = open("input1.txt","r")
n = int(sys.stdin.readline())
 
# map 정보 저장
graph = []
for i in range(n):
    graph.append(list(map(int,input())))
 
# 모든 경로에 대해 탐색해야 하므로 dfs가 좋다.
total_obstacle = 0 # 총 장애물 갯수
cnt_obstacle = 0 # 각각 장애물의 수
array = [] # 각각 장애물의 수 를 저장시킬 빈 리스트
def dfs(x,y):
    # 경로 끝에 가면 멈춘다.
    global cnt_obstacle
    if x<=-1 or y<= -1 or x>=n or y>=n:
        return False
    # 자신이 도로라면
    if graph[x][y]==1:
        graph[x][y]=0
        dfs(x+1,y)
        dfs(x, y+1)
        dfs(x-1, y)
        dfs(x, y-1)
        cnt_obstacle += 1
        return True
 
for i in range(n):
    for j in range(n):
        if dfs(i,j) == True:
            total_obstacle += 1
            array.append(cnt_obstacle)
            cnt_obstacle = 0
print(total_obstacle)
array.sort()
for i in range(total_obstacle):
    print(array[i])