난이도

Silver 1

풀이 참고 유무

x

막힌 부분

x

문제

문제 바로가기

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력

3
7
8
9

문제 검토

기본적인 dfs 문제이다.

풀이(python)

Python

#아이디어:  이중 for 문으로 모든 노드에 대하여 1이면서 방문하지 않았으면 방문 ,방문 처리 할때마다 카운트 +1
#시간복잡도:  2중 for문 25*25*(DFS 25x25 + 4x25x25 시간 복잡도 충분) 최악의 경우 39,453,125 < 1억
#자료구조: int[][] : matrix , int[][]: 방문확인
import sys
input=sys.stdin.readline
n=int(input())
matrix=[list(map(int,input().strip())) for _ in range(n)]
visited=[[0 for _ in range(n)] for _ in range(n)]
cnt=0
def dfs(x,y,depth):
    global cnt
    if x<0 or x>=n or y<0 or y>=n:
        return
    #방문한 곳이면 리턴
    if visited[x][y]!=0:
        return
    #그림이 아니면 리턴
    if matrix[x][y]==0:
        return
    #범위를 넘었다면 리턴
    #그림의 일부분이라면 방문처리 후 다음 노드 탄색 
    visited[x][y]=1
    cnt+=1
    dfs(x+1,y,depth+1)
    dfs(x,y+1,depth+1)
    dfs(x-1,y,depth+1)
    dfs(x,y-1,depth+1)
    return
answer=[]
result=0
for x in range(n):
    for y in range(n):
        cnt=0
        #방문하지 않은 그림 노드에 대해 dfs시작
        if visited[x][y]==0 and matrix[x][y]!=0:
            dfs(x,y,0)
            result+=1    
            answer.append(cnt)
print(result)
answer=sorted(answer)
for x in answer:
    print(x)

#아이디어
이중 for 문으로 모든 노드에 대하여 1이면서 방문하지 않았으면 방문 ,방문 처리 할때마다 카운트 +1

#시간 복잡도
2중 for문 25*25*(DFS 25x25 + 4x25x25 시간 복잡도 충분) 최악의 경우 39,453,125 < 1억

자료구조
자료구조 : int[][] : matrix , int[][]: 방문확인

걸린 시간

17:47

총평

기본적인 dfs로 강의에서 배운 문제 풀이 전략을 사용하는 것을 연습해보았다.