🔍 Problem

2667 단지 번호 붙이기

---

📃 Input&Output

---

📒 해결과정

1️⃣ 매트릭스의 최대 크기가 25 X 25 이기 때문에, 모든 좌표를 접근해도 타임오버가 나지 않는다. 따라서 방문하지 않고 값이 "1"인 좌표만 BFS를 시작한다.
2️⃣ 해당 섹션을 BFS로 시작하는데, 다음과 같다.
  ➊ 🧳 큐에 초기 위치를 넣고 방문처리를 한다.  
  ➋ 🔍 큐가 빌 때까지 그래프 탐색을 한다는 것은 특정 섹션에서만 BFS가 이루어진다는 것을 의미하므로 큐가 빌 때까지 다음 과정을 반복한다.  
      ① ➕ 큐에서 하나 꺼내고 방문 카운트를 1 올린다.  
      ② ↔️ 상하좌우 좌표를 탐색하는데, 다음 조건에 만족하면 큐에 넣고 방문 처리를 한다.  
  ➌ 🏁 큐가 전부 비었다면 result에 방문 카운트를 넣는다.  
  ➍ 📊 큐의 길이와 오름차순으로 정렬된 큐를 for문을 사용하여 출력한다.

---

❗주의점

1. 방문처리를 좌표가 큐에 들어갔을 때 수행한다.

   방문처리를 큐에서 나온순간 하면 나중에 큐에 들어갈 좌표들이 중복으로 처리되는 경우가 있기 때문이다.

---

💻 Code

import sys
from collections import deque


# 큐에 넣은 순간 방문처리!!

N = int(sys.stdin.readline())

mat = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
vst = [[False] * N for _ in range(N)]


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

result = []


def BFS(x, y):
    que = deque([])
    vst_cnt = 0
    que.append((x, y))
    vst[x][y] = True

    while que:
        now_x, now_y = que.popleft()
        vst_cnt += 1

        for i in range(4):
            next_x, next_y = now_x + dx[i], now_y + dy[i]
            if next_x >= 0 and next_y >= 0 and next_x < N and next_y < N:
                if vst[next_x][next_y] == False and mat[next_x][next_y] == 1:
                    que.append((next_x, next_y))
                    vst[next_x][next_y] = True

    result.append(vst_cnt)


for i in range(N):
    for j in range(N):
        if mat[i][j] == 1 and vst[i][j] == False:
            BFS(i, j)


print(len(result))
result.sort()

for i in result:
    print(i)

---

🤔 느낀점

가. 탐색 중 조건이 만족하고 좌표를 큐에 넣는 순간 방문처리를 해야 나중에 큐에 중복된 좌표가 들어오진 않는다. 큐에서 꺼내는 순간 방문하는 것이 아니라 큐에 넣는 순간 방문했다고 인지하는 것이 옳은 방법이다.

나. 마지막에 result을 정렬하지 않고 출력해서 3%에서 자꾸 오류가 났다. 문제를 잘 읽어봐야겠다.😅

---

📝 출처

여백