[알고리즘][Python] 백준 2667 단지번호붙이기 문제 풀이

문제 출처 : www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

---

문제 해석 : 붙어있는 집끼리 같은 단지로 취급하여 몇개의 단지가 있는지 단지 번호 몇개의 집이 있는지 출력하는 문제이다.

 

문제 풀이 :  BFS를 통해서 간단하게 문제를 풀이할 수 있다.

 

가능한 다른 풀이 : DFS도 이용가능하지만 BFS가 더 적당할 것 같다.

 

---

풀이 코드

from collections import deque


def BFS(a, b, count):
    global visited

    Q = deque()
    Q.append((a, b))
    visited[a][b] = count

    while Q:
        x, y = Q.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < N and 0 <= ny < N:
                if visited[nx][ny] == 0 and arr[nx][ny] == 1:
                    Q.append((nx, ny))
                    visited[nx][ny] = count


N = int(input())
arr = [list(map(int, list(input()))) for _ in range(N)]
visited = [[0] * N for _ in range(N)]
count = 1
dx = [0,0,-1,1]
dy = [1,-1,0,0]

for i in range(N):
    for j in range(N):

        if arr[i][j] == 1 and visited[i][j] == 0:
            BFS(i,j,count)
            count += 1

sum = 0
answer = []
for i in range(1, count):
    for a in range(N):
        for b in range(N):
            if visited[a][b] == i:
                sum += 1
    answer.append(sum)
    sum = 0

answer.sort()
print(count-1)
for element in answer:
    print(element)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.