티스토리 뷰

"""
 *packageName    : 
 * fileName       : 2667_단지번호붙이기_S1
 * author         : ipeac
 * date           : 2022-04-19
 * description    :
 * ===========================================================
 * DATE              AUTHOR             NOTE
 * -----------------------------------------------------------
 * 2022-04-19        ipeac       최초 생성
 """
from collections import deque


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

n = int(input())

graph = [list(map(int, input())) for _ in range(n)]


def bfs(a, b):
      queue = deque()
      
      # 초기
      queue.append((a, b))
      
      # 초기방문지점 방문처리
      graph[a][b] = 0
      
      count = 1
      
      while queue:
            x, y = queue.popleft()
            
            if x < 0 or y < 0 or x >= n or y >= n:
                  break
            
            for i in range(4):
                  nx = x + dx[i]
                  ny = y + dy[i]
                  
                  if nx < 0 or nx >= n or ny < 0 or ny >= n:
                        continue
                  
                  if graph[nx][ny] == 1:
                        graph[nx][ny] = 0
                        queue.append((nx, ny))
                        count += 1
      
      return count


for i in range(n):
      for j in range(n):
            if graph[i][j] == 1:
                  res.append(bfs(i, j))
print(len(res))
res.sort()
for num in res:
      print(num)

 - BFS

'코딩테스트 > 백준' 카테고리의 다른 글

[파이썬]1743_음식물 피하기_S1  (0) 2022.04.29
[파이썬]1697_숨바꼭질_S1.py  (0) 2022.04.19
[파이썬]트리의_부모_찾기_S2_DFS  (0) 2022.04.08
[파이썬] 4963_섬의개수_S2  (0) 2022.04.07
[파이썬]1260_DFSBFS_S2  (0) 2022.04.07
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/02   »
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
글 보관함