-
[Python] 백준 - 2667 단지번호 붙이기__Python/__Algorithm 2022. 1. 7. 16:51
# 실버 1
[문제]
링크 : https://www.acmicpc.net/problem/2667
문제 풀이
- 그래프탐색
- BFS
구현 코드
import sys from collections import deque def bfs(i,j): cnt = 0 queue = deque([[i,j]]) chk[i][j] = 1 while queue: x, y = queue.popleft() cnt+=1 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] for k in range(4): nx = x + dx[k] ny = y + dy[k] if (0<=nx<N) & (0<=ny<N): if (Graph[nx][ny] == 1) & (chk[nx][ny] == 0): queue.append([nx,ny]) chk[nx][ny] = 1 apt.append(cnt) N = int(sys.stdin.readline()) Graph = [list(map(int,sys.stdin.readline().strip())) for _ in range(N)] chk = [[0]*N for _ in range(N)] apt = [] for i in range(N): for j in range(N): if (Graph[i][j] == 1) & (chk[i][j] == 0): bfs(i,j) apt.sort() print(len(apt)) print(*apt,sep='\n')
실행 결과
728x90'__Python > __Algorithm' 카테고리의 다른 글
[Python] 백준 - 11286 절댓값 힙 (0) 2022.01.07 [Python] 백준 - 1927 최소 힙 (0) 2022.01.07 [Python] 백준 - 9020 골드바흐의 추측 (0) 2022.01.07 [Python] 백준 - 2178 미로 탐색 (0) 2022.01.07 [Python] 백준 - 1904 01타일 (0) 2021.12.21