[baekjoon] 2667. 단지 내 수 세기

문제

 

입력

 

예제입력, 예제 출력

---

로직

1. board에서 1이 나오면 그 주변을 bfs로 1인곳 확인

2. 확인한 곳의 숫자를 0으로 표시해 지나갔음을 표현, cnt += 1하면서

   최종 나온 값을 result리스트에 넣어서 오름차순으로 정렬 (오름차순 안해서 틀림!)

 

 

코드

N = int(input())
board = [list(map(int, input())) for _ in range(N)]

near = [(0, -1), (0, 1), (1, 0), (-1, 0)]

result = []
for i in range(N):
    for j in range(N):
        if board[i][j] == 1:
            cnt = 1
            q = [[i, j]]
            board[i][j] = 0

            while q:
                x, y = q.pop(0)
                for a, b in near:
                    xi, yi = x + a, y + b
                    if 0 <= xi < N and 0 <= yi < N:
                        if board[xi][yi] == 1:
                            cnt += 1
                            board[xi][yi] = 0
                            q.append((xi, yi))

            result.append(cnt)

result.sort()

print(len(result))
for i in result:
    print(i)

주의사항

1. bfs/dfs의 가장 기본 중의 기본문제.

2. 알고리즘을 너무 못해서 처음부터 다시시작.

3. dfs로 푸나, bfs로 푸나 차이를 모르겠다... -> bfs가 바로 주변을 찾아가면서 내려가니까 조금 더 빠를수도,,?