[BOJ] 2667. 단지번호붙이기

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

2667번: 단지번호붙이기

 

1. 해결방법

"""
1. 아이디어
- 2차원 배열 : int[][]
- 방문 기록 : bool[][]
- BFS를 돌면서 지도 각 단지의 연결된 아파트의 수를 구함.
- 구한 아파트 수를 오름차순으로 출력. : sort()

2. 시간복잡도
- O(V + E)
- V : 25 X 25 = 25^2
- E : 4 X 25 X 25 = 4 X 25^2

3. 자료구조
- BFS(Queue)
- 2차원 배열 : int[][]
"""

 

 

2. 정답 코드

입력 예제

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

 

출력 예제

3
7
8
9

 

 

코드

from collections import deque

n = int(input())
map = [list(map(int, input())) for _ in range(n)]
chk = [[False] * n for _ in range(n)]

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

# bfs
def bfs(y, x):
    q = deque()
    q.append((y, x))
    apt = 1
    while q:
        ey, ex = q.popleft()
        for k in range(4):
            ny = ey + dy[k]
            nx = ex + dx[k]
            if 0 <= ny < n and 0 <= nx < n:
                if map[ny][nx] == 1 and chk[ny][nx] == False:
                    apt += 1
                    chk[ny][nx] = True
                    q.append((ny, nx))

    return apt


# 단지 수 리스트
number = []

# main
for j in range(n):
    for i in range(n):
        if map[j][i] == 1 and chk[j][i] == False:
            chk[j][i] = True
            number.append(bfs(j, i))

number.sort()
print(len(number))
for i in range(len(number)):
    print(number[i])

 

list.sort()와 sorted(list)의 차이점을 알고 있지 못해서 틀린 문제였다.