알고리즘 Archive
[백준] 2667 - 단지번호붙이기
희롭
2021. 3. 24. 22:07
n = int(input())
mapp = []
result = 0
real = 0
total = []
for i in range(n):
mapp.append(list(map(int, input())))
def house(x, y):
if x<=-1 or x>=n or y<=-1 or y>=n:
return False
if mapp[x][y]==1:
mapp[x][y]=0
global result
result += 1
house(x-1,y)
house(x+1,y)
house(x,y-1)
house(x,y+1)
return result
return False
for i in range(n):
for j in range(n):
a = house(i,j)
if a != False:
total.append(a)
result = 0
real+=1
print(real)
for i in sorted(total):
print(i)
* 풀이 평가 : 약 30분 이상 걸려서 (말미에 살짝 졸긴 했지만) 풀었다!!! (솔브 뜬거 보고 잠깸 ㅋㅋ)
* 풀이 아이디어 : 각 단지의 집 count 해주면서, 단지의 개수 하나 추가될때마다 집 카운트하던거 따로 리스트에 저장한 후 초기화해서 다시 새 단지 집 count하는거 반복하는식! sorted 적절했음!
* 다른 사람 아이디어 신기했던 거 : 집 개수랑 단지 개수를 한 list에 넣어서 세더라... 이때, 단지 개수는 계속 list[0]에 위치하도록(list=list+[0]해주면서) 하고, "list[0]=현재까지 count된 단지 개수"인 점 이용해서, 집 개수가 list[list[0]]에서 count되도록 함! ex) 단지 개수 3개면, list[0]=3이고, 따라서 재귀함수에서 list[3]+=1 되도록 집개수 count함. (https://www.acmicpc.net/source/24267221)