[파이썬] 백준 2667 : 단지 번호 붙이기(BFS)

[파이썬] 백준 2667 : 단지 번호 붙이기(BFS)

2667번: 단지번호붙이기 (acmicpc.net)

2667번: 단지번호붙이기

실버 1

그래프, BFS

---

접근

그래프 이론 문제중에 양이라는 문제와 비슷한 유형이다.

지정된 범위안에서 좌표에 따라 bfs 탐색을 시키면서 1이 있을때마다 그 개수를 카운팅한 후 반환하면 집의 개수를 출력하도록 할 수 있다.

bfs 탐색이 종료될 때마다 집의 개수를 반환하므로, 이는 곧 단지 하나에 대한 탐색을 끝마쳤다는 뜻과 같기 때문에 집의 개수를 담을 리스트의 길이를 단지의 개수로 나타낼 수 있다.

 

BFS 코드

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

N = int(input())
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(b_x, b_y, N):
    queue = deque()
    queue.append([b_x, b_y])
    visited[b_x][b_y] = 1

    home_cnt = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            ddx = dx[i] + x;
            ddy = dy[i] + y;
            if 0 <= ddx < N and 0 <= ddy < N:
                if visited[ddx][ddy] == 0 and field[ddx][ddy] == 1: // 두 조건문을 한줄에 합쳐 쓰면 ddx와 ddy가 범위를 초과할 때 인덱싱 에러가 날 수 있다.
                    home_cnt +=1
                    queue.append([ddx, ddy])
                    visited[ddx][ddy] = 1
    return home_cnt

lst = []
field = []
group_cnt = 0

for _ in range(N):
    field.append(list(map(int, input().rstrip())))

visited = [[0]* N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if visited[i][j] == 0 and field[i][j] == 1:
            lst.append(bfs(i, j, N))
print(len(lst))
lst.sort()
for l in lst:
    print(l)