[백준 ] 2667 단지번호붙이기 (BFS)

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

2667번: 단지번호붙이기

 

bfs 알고리즘을 이용하여 풀었다. 

 

""" 백준 2667 단지번호붙이기
1. 아이디어
- 방문 여부(chk), 길이 맞는지(map 값이 1인지)
- BFS 돌면서 총 갯수 + 1, 각각 값 저장

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

3. 자료구조
- 그래프 전체 지도: int[][]
- 방문 여부: bool[][]

 

4. 로직 순서

1) 미로판 범위 내에서

2) map[0][0] 부터 bfs를 이용해 동,서,남,북 4방향을 검사하여, 
 길이 존재 하고(map[j][i] 값이 1), 방문하지 않은 곳(chk[j][i] == False) 을 찾는다.

3) 2)의 경우, 카운트 값(rs)을 올려주고, 방문한 곳으로 값을 변경(chk[j][i] = True)한다.

4) 해당값을 ans 에 append 하면서 각 단지 내 값을 더해준다.

 

5. 발생했던 오류

1) n 값을 하나만 받아오는 방법을 몰랐다.  -> 검색을 통해 해결

2) 각 단지 내 값들을 출력하는 방법을 몰랐다. 

아래 처럼 입력하게 되면, ans 리스트의 첫번째 요소부터 마지막 요소까지 출력한다는 의미임.

for k in ans:
    print(k)

"""

 

---

from collections import deque

import sys
input = sys.stdin.readline

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

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


def bfs(y,x):
    rs = 1

    q = deque()
    q.append((y,x))

    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:
                    rs += 1
                    chk[ny][nx] = True
                    q.append((ny,nx))

    return rs

cnt = 0
ans = []

for j in range(n):
    for i in range(n):
        if map[j][i] == 1 and chk[j][i] == False:
            chk[j][i] = True
            cnt += 1
            ans.append(bfs(j, i))
ans.sort()

print(cnt)
for k in ans:
    print(k)