백준 파이썬 2667번 : 단지번호 붙이기 풀이

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

2667번: 단지번호붙이기

그래프 탐색 문제로, 동서남북으로 인접한 곳에 집이 있으면(= 1이라면) 집이 연결되어 있다고 하고, 연결된 집의 모임을 단지라고 한다. 여기서 단지의 개수, 각 단지내 집의 수를 출력해야 한다.

 

1. 어느 한 점에 대해서 인접한 곳에 1이 있는지를 탐색하고

2. 1이 있다면 그 점에서 다시 인접한 곳을 탐색하길 반복하고

3. 탐색을 할 때마다 카운트를 세다가

4. 탐색이 끝나면 카운트를 정답에 저장해준다 

graph = [] 
n = int(input())
answer = [] 
dx = [0,0,1,-1] #동서남북 인접한 곳의 좌표를 구하기 위함 
dy = [1,-1,0,0]
cnt = 0 
for _ in range(n):
    x = list(map(int,input()))
    graph.append(x)
def dfs(x,y):
    global cnt
    graph[x][y] = '#'
    cnt += 1 #탐색을 시작할 때마다 카운트를 더해준다 
    for k in range(4): #동서남북 인접한 네 방향에 대해서 
        nx = x + dx[k]
        ny = y + dy[k]
        if 0<=nx<n and 0<=ny<n and graph[nx][ny] ==1: #인접한 곳의 좌표가 범위 내이고, ==1이라면 
            graph[nx][ny] = '#' #방문한 곳으로 처리해준다 
            dfs(nx,ny) #조건을 만족하는 지점에서 다시 탐색을 시작한다 
    return cnt 
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            cnt = 0
            answer.append(dfs(i,j))
print(len(answer))
answer.sort()
for i in answer:
    print(i)