[백준-파이썬] 2667번: 단지번호 붙이기

백준 2667번 문제 보기~

📌 포인트

DFS로 풀었다!

🤨 헷갈렸던 부분

• 입력이 '0110100'이런 식으로 띄어쓰기 없이 들어옴. split하면 안됨! 처음에 split해서 계속 에러가 나왔다.ㅠ

👩‍💻 코드와 설명

dx=[-1,0,1,0]
dy=[0,1,0,-1]

def DFS(x,y):
    global cnt

    for i in range(4): #상하좌우를 체크!
        xx=x+dx[i]
        yy=y+dy[i]

        if 0<=xx<n and 0<=yy<n and board[xx][yy]==1: #인덱스 범위 안이고, 집을 발견하면
                cnt += 1
                board[xx][yy] = 0
                DFS(xx,yy)

if __name__=='__main__':
    n=int(input())
    board=[list(map(int,input())) for _ in range(n)]

    cntList=[]

    for i in range(n):
        for j in range(n):
            if board[i][j]==1: #집 하나 발견 시!
                cnt=1 #갯수를 1로 초기화(일단 하나 찾았으니까)
                board[i][j] = 0 #그 부분을 0으로 바꿈(다시 세지 않도록)
                DFS(i,j) #집 하나 발견한 위치에서 DFS 시작
                cntList.append(cnt) #DFS 끝나면 cnt를 cntList에 추가함


    cntList.sort() #오름차순 정렬
    print(len(cntList)) #총단지 수 출력
    for x in cntList: #하나씩 출력
        print(x)