[Python]DFS와BFS 백준 2667

 문제

 https://www.acmicpc.net/problem/2667

DFS BFS 모두 사용이 가능하다.

나는 DFS를 사용하여 구현해 보았다.

import sys
N=int(sys.stdin.readline())
map=[]
for i in range(N):
    row=sys.stdin.readline()
    tmp=[]
    for i in range(N):
        tmp.append(int(row[i]))
    map.append(tmp)
 
 
def area(start_row,start_colume,map):#아래위 좌우 확인 dfs를 통해 확인
    count=1
    map[start_row][start_colume] = 2
    if start_row+1<N and map[start_row+1][start_colume]==1:#아래확인 연결되어있으면
        count+=area(start_row+1,start_colume,map)#아래노드에서 다시확인
 
 
    if start_row-1>=0 and map[start_row-1][start_colume]==1:#위확인 연결되어있으면
        count+=area(start_row-1,start_colume,map)
 
 
    if start_colume+1<N and map[start_row][start_colume+1]==1:#오른쪽 확인 연결되어있는지
        count+=area(start_row,start_colume+1, map)
 
 
    if start_colume-1>=0 and map[start_row][start_colume-1]==1:#왼쪽 확인 연결되어있는지
        count+=area(start_row,start_colume-1, map)
 
 
    return count
 
cnt=0
result=[]
 
for i in range(N):
    for j in range(N):
        if map[i][j]==1:
            result.append(area(i,j,map))
            cnt+=1
 
 
print(cnt)
result.sort()
for i in result:
    print(i)