백준2667(파이썬) - 단지번호붙이기

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

2667번: 단지번호붙이기

• 아주 전형적인 DFS/BFS 문제였다. 나는 DFS로 풀었다.
• 항상 dfs(x-1,y), dfs(x+1,y), dfs(x,y+1), dfs(x,y-1) 이런식으로 재귀를 이용했는데 요즘 dx,dy를 이용한 방법으로 연습하고 있다.
• 2583번의 영역구하기랑 dfs를 구현하는 부분에서는 그냥 똑같다고 볼 수 있다.
• dfs함수 안에서는 이동하려는 배열안의 값이 1이면, 계속해서 재귀를 돌리고 0일 경우에 끝나게 된다. 이 부분에서 0일 경우에 끝나면 여태까지 dfs를 돌렸던 카운트를 더해서 리스트안에 넣어두는 방식을 사용하였다. 
• 문제에서 그냥 오름차순으로 정렬해서 풀라고 하였지만 예를 들어 특정 인덱스의 값을 출력하라는 문제가 나오면 리스트에 인덱스를 부여하고 그 인덱스에 해당하는 배열 안에 값을 넣어주면 될 거 같다.

import sys
input = sys.stdin.readline


n = int(input())
data = []
for _ in range(n):
    data.append(list(input()))

dx = [1,-1,0,0]
dy = [0,0,1,-1]

num_list = []

def dfs(x,y):
    global cnt
    cnt += 1
    data[x][y] = '0'
    for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<n:
                if data[nx][ny] == '1':
                    dfs(nx,ny)

for i in range(n):
    for j in range(n):
        if data[i][j] == '1':
            cnt = 0
            dfs(i,j)
            num_list.append(cnt)
            
num_list.sort()
print(len(num_list))
for i in num_list:
    print(i)