Problem

0과 1로 이루어진 2차원 N*N 배열에서 1이 상하좌우로 연결되어있는 부분과 각각의 개수 구하기

Solution

1)DFS로 탐색 (visited배열 이용)

코드설명

1)visited배열과 원본 배열을 이용하여 DFS실행
2)원본배열에서 1이고 방문 하지 않았으면=>DFS함수로 들어가 이어진곳 탐색
3)각 이차원 배열을 돌면서 2)의 과정 수행

Python Code

# https://www.acmicpc.net/problem/2667
import sys

N=int(sys.stdin.readline())
arrList=[list(map(int,input())) for _ in range(N)]
visited=[[False]*N for _ in range(N)]


dx=[-1,0,1,0]
dy=[0,-1,0,1]
result=[]
def dfs(y,x):
    if not visited[y][x]:
        visited[y][x]=True

        for i in range(0,4):
            tmpy=y+dy[i]
            tmpx=x+dx[i]

            if tmpy<0 or tmpx<0 or tmpy>N-1 or tmpx>N-1:
                continue
            if not visited[tmpy][tmpx] and arrList[tmpy][tmpx]==1:
                result[len(result)-1]+=1
                dfs(tmpy,tmpx)


for i in range(len(arrList)):
    for j in range(0,len(arrList[i])):
        if arrList[i][j]==1 and not visited[i][j]:
            result.append(1)
            dfs(i,j)
result.sort()
print(len(result))
for re in result:
    print(re)