백준/ Silver 1 문제 , 백준 파이썬 2667 , 단지번호붙이기 [BFS]

백준/ Silver 1 문제 , 백준 파이썬 2667 , 단지번호붙이기

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
BFS 를 사용하여 풀자.

 

 

<문제 출처>

 

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

2667번: 단지번호붙이기

------------------------------------------------------------------------------------------------------------------------------

 

 

1을 만나면 그 주위의 단지들을 다른숫자로 바꿔준다.

 

어차피 초기에는 다 1로 설정되어있으니까 2부터 시작해서 숫자들을 부여해주면 된다.

 

(2단지, 3단지, 4단지....)

 

이때 deque를 사용해서 인접한 집들로 퍼지듯이 숫자들을 변경시켜주면 된다.

 

이후 단지 갯수를 출력해주고

 

각 단지가 몇개 씩있는지 answer 배열에 따로 저장해주었다.

 

이후 정렬 후 하나씩 출력해주면 된다.

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

from collections import deque

N=int(input())
place=[]
for i in range(N):
    place.append(list(map(int,input())))

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]
dq=deque()

def numChange(i,j,cnt):
    dq.append([i,j])
    while dq:
        i,j=dq.popleft()
        for k in range(4):
            move_x=i+vertical[k]
            move_y=j+parallel[k]
            if 0<=move_x<N and 0<=move_y<N:
                if place[move_x][move_y]==1:
                    place[move_x][move_y]=cnt
                    dq.append([move_x,move_y])

cnt=2
for i in range(N):
    for j in range(N):
        if place[i][j]==1:
            place[i][j]=cnt
            numChange(i,j,cnt)
            cnt+=1

complex=cnt-2
print(complex)
num=2
answer=[]
for i in range(complex):
    result=0
    for j in range(N):
        result+=place[j].count(num)
    answer.append(result)
    num+=1

answer.sort()
for i in range(complex):
    print(answer[i])