[알고리즘] 백준 2667 파이썬 - 단지번호붙이기

 

2667번: 단지번호붙이기

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

 

문제풀이

from collections import deque
n=int(input())
graph=[]
for i in range(n):
    graph.append(list(map(int,input())))

def bfs(x,y):
	#01
    dx=[0,0,-1,1]
    dy=[-1,1,0,0]
    q=deque([(x,y)])
    graph[x][y]=0
    cnt=1
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            #02
            if 0<=nx<n and 0<=ny<n and graph[nx][ny]==1:
                graph[nx][ny]=0
                q.append((nx,ny))
                cnt+=1
    return cnt
ans=[]
#03
for i in range(n):
    for j in range(n):
        if graph[i][j]==1:
            ans.append(bfs(i,j))
#04
ans.sort()
print(len(ans))
print(*ans,sep="\n")

- #01 : 움직일 수 있는 경우인 dx와 dy를 정의해주고, q에 초기값으로 (x,y)를 저장한다.

           이후 graph[x][y] 즉 1인 값을 0으로 바꿔주고 cnt는 1로 시작한다.

- #02 : nx와 ny가 범위 안의 값이고, graph[nx][ny]가 1이라면,

           graph[nx][ny]를 0으로 바꾸고, q에 추가하고 cnt를 1 더해준다.

           while문이 끝나면 cnt를 반환한다.

- #03 : for문으로 i와 j값을 바꿔가며 만약 graph[i][j]가 1이라면 bfs 함수를 실행하여

           얻은 값을 ans에 추가한다.

          참고로 bfs 실행 시 주변에 붙은 1 값은 모두 0으로 바뀌고 cnt에 추가되기에,

          서로 근접하지 않은 즉 단지별로 cnt의 개수를 구할 수 있는 것이다.

- #04 : 얻은 ans를 오름차순 정렬하고, ans의 길이를 출력 후,

           \n을 기준으로 ans의 값들을 순서대로 출력해준다.