알고리즘 PS
[Python] 백준 #2667 단지번호붙이기
on_doing
2021. 1. 16. 19:01
728x90
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
정답률이 꽤 낮은 문제이지만, dfs/bfs를 잘 이용하면 그리 어렵지않은 문제이다
from collections import deque
import sys
def DFS(i, j):
que = deque()
if i < 0 or i >= n or j < 0 or j >= n:
return None
else:
cnt = 0
if List[i][j] == 1:
que.append([i, j])
List[i][j] = 0
while que:
p = que.popleft()
xx = p[0]
yy = p[1]
cnt += 1
for k in range(4):
x = dx[k]
y = dy[k]
if xx + x < 0 or xx + x >= n or yy + y < 0 or yy + y >= n:
continue
else:
if List[xx + x][yy + y] == 1:
que.append([xx + x, yy + y])
List[xx + x][yy + y] = 0
return cnt
else:
return None
n = int(sys.stdin.readline().rstrip())
List = []
result = []
for i in range(n):
List.append(list(map(int, sys.stdin.readline().rstrip())))
# 상,하,좌,우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
p_cnt = 0 # 단지 내 아파트
for i in range(n):
for j in range(n):
k=DFS(i,j)
if k == None:
continue
else:
result.append(k)
p_cnt += 1
print(p_cnt)
result=sorted(result)
for i in result:
print(i)728x90