단지번호붙이기 - 백준 2667번

문제에 설명에 나와있듯이 1은 집이 있는 곳을 나타내고 0은 집이 없는 곳을 나타낸다.

 

x축과 y축을 그려서 각 집마다 좌표를 구한다.

집이 있는 좌표만 배열에 담아서 DFS를 통해 문제를 해결할 수 있다.

 

 

 

n = int(input())
arr = []
for _ in range(n):
    p = input()
    arr.append(p)
x = 0
y = 0
cordinate = []
for i in arr:
    for j in i:
        if j == '1':
            cordinate.append([x,y])
        x+=1
    y+=1
    x=0
# print(cordinate)

def search(mainList):
    # 입력받은 배열이 비어있으면 종료
    if mainList == []:
        return 'end'
    villageCount = 0
    villagePeoples = []
    while len(mainList) > 0:
        standard = mainList[0]  # 기준은 배열의 0번 인덱스
        mainList = mainList[1:] # 기준으로 잡은 좌표는 삭제
        village = [standard]    # 단지 배열생성, 0번 인덱스 위치에 기준을 넣어준다.

    
        for i in village:

            up = [i[0],i[1]-1]      # 윗 집 좌표
            down = [i[0],i[1]+1]    # 아래 집 좌표
            left = [i[0]-1,i[1]]    # 왼쪽 집 좌표
            right = [i[0]+1,i[1]]   # 오른쪽 집 좌표

            # 위에서 미리 만들어둔 좌표로 탐색
            # 만약 집이 있으면 village 배열에 추가하고 입력받은 mainList에서는 삭제
            if mainList.count(up) == 1 and up not in village:
                village.append(up)
                mainList.remove(up)
            if mainList.count(down) == 1 and down not in village:
                village.append(down)
                mainList.remove(down)
            if mainList.count(left) == 1  and left not in village:
                village.append(left)
                mainList.remove(left)
            if mainList.count(right) == 1 and right not in village:
                village.append(right)
                mainList.remove(right)
        villageCount += 1
        villagePeoples.append(len(village))
    # print('debugPrint',len(mainList))
    # if len(mainList) > 0:
    #     search(mainList)
    # else:
    #     return "end"

    # return village, mainList, villageCount, villagePeoples
    return villageCount, villagePeoples
# print('search',search(cordinate))
villageCount = search(cordinate)[0]
villagePeoples = search(cordinate)[1]
villagePeoples.sort()
print(villageCount)
for i in villagePeoples:
    print(i)

 

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기