[백준] 2667 - 단지번호붙이기

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

 

 

알고리즘

DFS, BFS

 

풀이

연결요소의 개수(총 단지수)와 연결요소에 속하는 정점의 개수(단지내 집의 수)를 구하는 문제이다.

이중 for 문을 돌려 새롭게 bfs 탐색을 시작할 때, 새로운 연결요소의 시작이라고 판단해 연결요소의 개수에 +1을 해주었다. (코드에서 연결요소의 개수는 ans) 

bfs 내에 d 라는 변수를 선언해 한 연결요소를 순회할 때, (=새로운 정점으로 이동할 때) +1을 해주었다. 쉽게 말하면 방문 처리를 할 때 +1을 해주었다. dq에 아무값도 없을 때 d를 return 했다. 

 

전체 코드

# 단지번호붙이기
# 연결요소의 개수(ans), 각 연결요소에 해당하는 개수(res)
from collections import deque 

N = int(input())

board = [list(input()) for _ in range(N)]

def is_valid_coord(y, x):
    return 0 <= y < N and 0 <= x < N

dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)

ans = 0 # 총 단지수 
res = [] # 단지내 집의 수 

def bfs(x, y):
    dq = deque()
    dq.append((x, y))
    d = 1 
    
    while dq:
        x, y = dq.popleft()
        
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            
            if is_valid_coord(ny, nx) and board[nx][ny] == '1':
                dq.append((nx, ny))
                board[nx][ny] = '0'
                d += 1 
                
    return d 
    
for i in range(N):
    for j in range(N):
        if board[i][j] == '1':
            board[i][j] = '0'
            num = bfs(i, j)
            ans += 1 
            res.append(num)

print(ans)

for num in sorted(res):
    print(num)