문제

주요 로직을 생각해보자.

1번: 막생각 나는 대로 | O(n^3)

  • 2차원 배열을 입력 받는다.
  • 방문 여부를 const로 설정한다.
  • 2차원 배열을 순회한다.
    • 1이 아니면 통과한다.
    • 상하좌우 탐색한다.
    • dfs로 집 수를 찾는다.
    • 집수 list에 저장한다.
  • 집수 list를 정렬한다.
  • 집수를 출력한다.

구현

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


TARGET = '1'
VISITED = -1
cost_list = []
directions = [
    [0, 1],
    [0, -1],
    [1,0],
    [-1,0]
]

def dfs(x,y):
    global n
    
    map_list[x][y] = VISITED
    
    localCount = 1
    for i in range(4):
        nx = x + directions[i][0]
        ny = y + directions[i][1]
        
        if nx < 0 or ny < 0 or nx >= n or ny >= n:
            continue
            
        if map_list[nx][ny] != TARGET:
            continue
        
        localCount += dfs(nx,ny)
        
    return localCount

for i in range(n):
    for j in range(n):
        if map_list[i][j] != TARGET:
            continue
        cost_list.append(dfs(i,j))

cost_list.sort()
print(len(cost_list))
for i in cost_list:
    print(i)

틀린 점

  • sorted()는 pure function이다.