코딩테스트/백준
[백준] 2667번 단지번호붙이기 / 파이썬(python)
Jiwon_C
2021. 5. 19. 22:34
# 문제 링크
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
# Soultion
DFS를 이용하여 푼 문제이다.
|
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
29
30
31
32
33
|
n = int(input())
graph = []
for _ in range(n):
graph.append(list(map(int,input())))
grp = []
cnt = 0
dx = [-1,1,0,0] # 상하좌우
dy = [0,0,-1,1]
def dfs(x,y):
global cnt
if x<0 or x>=n or y<0 or y>=n: # 범위
return False
if graph[x][y]==1:
cnt +=1
graph[x][y] = 0
for i in range(4):
dfs(x+dx[i],y+dy[i])
return True
for i in range(n):
for j in range(n):
if dfs(i,j)==True:
grp.append(cnt)
cnt = 0
print(len(grp))
grp.sort()
for i in grp:
print(i)
|
cs |
17. 단지의 집 개수를 구하기위해 카운팅을 해준다.
26. 한 개의 그룹이 완성되면 카운팅한 집의 개수를 리스트에 저장한 뒤, 0으로 초기화해준다.