백준 2667(단지번호 붙이기) - Python(파이썬) - BFS

2667번: 단지번호붙이기

예제 설명

이렇게 생긴 지도가 있다고 할 때 선분 하나를 공유하고 있는 경우에는 같은 단지이다.

출력으로 단지의 개수를 구하고 단지 안에 속하는 집의 수를 오름차순으로 정렬하여 출력하도록 한다.

문제 풀이

1) dfs 방식으로 풀기 

1️⃣ dfs 함수 만들기
   ① 재귀함수를 이용해서 풀기 때문에 함수를 실행 전에 지도안에 포함되는지를 확인 -> 아닐 경우 , return False
   ② 지도안에 포함될 경우 지도 안에 1로 표시된 집인지 확인 -> 아닐 경우, return False
   ③ 지도 안에 포함되고 집인 경우 집의수(cnt)를 하나 증가
   ④ for루프로 위,아래,오른쪽,왼쪽을 움직여서 같은 단지의 집을 찾기 위해 재귀함수를 호출
2️⃣ 같은 단지 내 집의 수를 구했으므로 sum 리스트에 append한 후 , 다른 단지내 집의 수를 세기 위해 cnt = 0으로 초기화
3️⃣ sum 리스트를 오름차순 정렬한 후 단지의 개수와 단지 안의 수를 출력

💻 Python(파이썬)

import sys
n = int(sys.stdin.readline())
array=[]
#지도
for i in range(n):
    array.append(list(map(int,sys.stdin.readline().strip())))

#위,아래,오른쪽,왼쪽으로 이동
d= [(1,0),(0,1),(-1,0),(0,-1)]
cnt=0

def dfs(y,x):
	#지도를 벗어나는 순가 멈춤
    if x<0 or x>=n or y<0 or y>=n:
        return False
    #집이면 수행
    if array[y][x]==1:
        global cnt
        cnt+=1
        #이미 집을 세었으므로
        array[y][x]=0
        #같은 단지의 집 찾기
        for dy,dx in d:
            dfs(y+dy,x+dx)
        return True
    return False

#단지내 집의 수
sum=[]
for i in range(n):
    for j in range(n):
        if dfs(i,j):
            sum.append(cnt)
            #다른 단지 집의수를 세기위해 초기화
            cnt=0

#오름차순 정렬
sum.sort()
#단지의 개수 , 단지내 집의 수
print(len(sum),"\n".join(str(i) for i in sum),sep="\n")

2) bfs 방식으로 풀기 

1️⃣ bfs 함수 만들기
   ① 지도 안에 1로 표시된 집인지 확인 -> 큐에 현재 위치하는 점을 append, 집의 수(cnt) 하나 증가, 이미 집을 방문하였으므로 지도안에 array[y][x] = 0으로 변경
   ② 큐에 숫자가 들어있는 동안까지 실행
        1) 큐에서 하나의 숫자 빼기
        2) 이 숫자가 지도안에 숫자인지 확인하고 집의 위치인지 확인 
        3) 집을 방문하였으므로 지도안에 array[dy][dx] = 0 으로 변경, 집의 숫자(cnt) +1 , 큐에 이동한 좌표 append
   ③ 단지의 수 반환
2️⃣ 단지의 수를 가지고 리스트 생성(count)
3️⃣ count 리스트를 오름차순 정렬한 후 단지의 개수와 단지 안의 수를 출력

import sys
from collections import deque
n = int(sys.stdin.readline())
array=[]
for i in range(n):
    array.append(list(map(int,sys.stdin.readline().strip())))

d= [(1,0),(0,1),(-1,0),(0,-1)]

def bfs(y,x):
    if array[y][x]==1:
        cnt = 1
        q = deque()
        q.append((y,x))
        array[y][x]=0
        while q:
            y1,x1 = q.popleft()
            for dy,dx in d:
                if (0<=x1+dx<n and 0<=y1+dy<n) and array[y1+dy][x1+dx]==1:
                    array[y1+dy][x1+dx]=0
                    cnt +=1
                    q.append((y1+dy,x1+dx))
    return cnt

count = [bfs(i,j) for i in range(n) for j in range(n) if array[i][j]==1]

count.sort()
print(len(count),"\n".join(str(i) for i in count),sep="\n")