[백준/2667/파이썬] 단지 번호 붙이기

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

2667번: 단지번호붙이기

 

DFS/BFS 문제 중에서, 연결요소 + 연결요소의 크기를 찾는 간단하지만, 중요한 개념이 있는 문제이다.

 

아래와 같이, 2차원 board를 직접 갖고노는 문제의 기본적인 아이디어

 

• Board 자체를 그래프로 본다.
• 칸의 배열 => 1개의 노드, 연결여부 -> edge로 생각

입력 예시를 보면, 주황색/초록색/파란색처럼, 아파트 단지가 3개가 생길거임!

SOL)

1. v_chk 배열에, True/False 형태보단, 정수형으로 선언해서, 각 아파트 단지의 번호를 붙여준다.

( True/False로 선언해도 됨! , 하지만, 난 나중에 apt의 정보를 쉽게 저장해주기 위해서, 이렇게 하겠음)

2. v_chk 배열에 , numbering한 아파트의 단지번호를 세어주고, apt 배열에 저장해줄거임.

3. cnt 변수를 하나 선언해서, 아파트 단지의 개수도 세어줄거임.

4. DFS/BFS 다 가능하지만, BFS로 풀어볼 거임.

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
board= [list(map(int,input().rstrip())) for _ in range(N)]
v_chk=[[0]*N for _ in range(N)]
apt=[]
dx=(1,0,-1,0)
dy=(0,1,0,-1)

def bfs(y,x,d):
    dq = deque()
    v_chk[y][x]=d
    dq.append([y,x])
    while dq:
        y,x=dq.popleft()
        for k in range(4):
            ny= y+dy[k]
            nx= x+dx[k]
            if (0<=ny<N and 0<=nx<N) and v_chk[ny][nx] == 0 and board[ny][nx] ==1:
                v_chk[ny][nx] =d
                dq.append([ny,nx])

def cnt_apt(d):
    total=0
    for i in range(N):
        for j in range(N):
            if v_chk[i][j]==d:
                total+=1
    return total


cnt=0
d=1
for i in range(N):
    for j in range(N):
        if board[i][j] == 1 and v_chk[i][j] ==0:
            bfs(i,j,d)
            apt.append(cnt_apt(d))
            d+=1
            cnt+=1
#apt.sort()
#sorted는 sorting된 객체를 반환하기 때문에, 반환을 받을 변수가 있어야함.
apt =sorted(apt)
print(cnt)
for i in range (len(apt)):
    print(apt[i])