12.단지 번호 붙이기(DFS)

문제 - 생략

 

문제풀이

import sys
sys.stdin=open("input.txt", "r")
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]

def DFS(x, y):
    global cnt
    cnt+=1                 #집좌표가 넘어 오면 카운팅
    board[x][y]=0          #이미 방문한 경우 흔적을 남긴다.
    for i in range(4):     #range의 범위만큼 자식이 생긴다
        xx=x+dx[i]
        yy=y+dy[i]
        if 0<=xx<n and 0<=yy<n and board[xx][yy]==1: #xx,yy좌표는 방문한 적이 없어야 한다. 
            DFS(xx, yy)    #재귀함수는 루트노드가 된다.                               

if __name__=="__main__":
    n=int(input())
    board=[list(map(int, input())) for _ in range(n)] #입력에 띄어쓰기가 없음에 주의한다. 
    res=[]
    for i in range(n):
        for j in range(n):
            if board[i][j]==1:
                cnt=0             #새로운 단지가 발견되는 경우 cnt=0부터 시작
                DFS(i, j)         #이중 for문을 돌면서 부모노드(단지) DFS가 여러 번 호출된다. 
                res.append(cnt)
    print(len(res))
    res.sort()
    for x in res:
        print(x)

 

 

Hint

 ▶ if 0<=xx<n and 0<=yy<n and board[xx][yy]==1:

   

    → next좌표인 xx, yy는 0보다 크거나 같아야하며, n보다 작아야 경계선 안에 움직인다.

    → next좌표는 board[xx][yy]로 이미 방문한 적이 없어야 한다. 
           

 

 

 ▶ DFS(xx, yy)                                   

   # board[xx][yy]=1   

   단지 내에 있는 집의 수를 카운팅하는 것이므로 중복해서 카운팅 하면 안된다.

   따라서  back할때 방문  방문흔적을 지우지 않고 남겨 놓는다. 흔적을 남겨놓는다. 

 

 

▶main 함수에서 이중for문을 돌면서 DFS를 여러번 호출하도록 만들수도 있다. (중요)