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

문제

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

풀이

• N$\times$N 단지
• 1: 집이 있는 곳, 0: 집이 없는 곳
• 연결된 집(단지)수 출력

이 문제는 그래프 탐색을 이용해 풀 수 있으며 저는 BFS로 풀어봤습니다.

그래프를 입력 받고 반복문을 통해 1이 발견되면 탐색 시작

graph = [list(map(int,input().rstrip())) for _ in range(n)]

for i in range(n):
	for j in range(n):
    	if graph[i][j] == 1:
        	bfs(i,j)

1의 좌표는 방문 처리
상하좌우를 탐색하여 범위 내에 있는 단지를 queue에 추가하여 계속해서 탐색
발견될 경우 cnt +1

def bfs(x,y):
	queue = deque([(x,y)])
    graph[x][y] == 0 # 현재 좌표 방문 처리
    cnt = 1 # 현재 좌표의 집을 발견해서 1로 선언
    
    while queue:
    	x,y = queue.popleft()
        
        # 상하좌우 탐색
        for i in range(4):
        	nx,ny = x+dx[i], y+dy[i]
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 1: # 범위 내 && 방문 가능한 경우
            	queue.append((nx,ny))
                graph[nx][ny] = 0 # 방문 처리
                cnt += 1 # 집수 +1
                
	return cnt

cnt값을 return 받았으니 이를 배열에 넣고 오름차순 정렬 후 출력해주면 해결 😋

res = []
for i in range(n):
	for j in range(n):
    	if graph[i][j] == 1:
        	res.append(bfs(i,j))
res.sort()

print(len(res))
for r in res:
	print(r)

코드

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

def bfs(x,y):
    queue = deque([(x,y)])
    graph[x][y] = 0
    cnt = 1

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx,ny = x+dx[i], y+dy[i]
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 1:
                queue.append((nx,ny))
                graph[nx][ny] = 0
                cnt += 1
    
    return cnt

if __name__ == "__main__":
    n = int(input())
    graph = [list(map(int,input().rstrip())) for _ in range(n)]

    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    res = []
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 1:
                res.append(bfs(i,j))
    res.sort()

    print(len(res))
    for r in res:
        print(r)