[Baekjoon Online Judge] 백준 2667번 단지번호붙이기(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2667번 단지번호붙이기

(Python)

(글쓴날 : 2020.03.28)

 

---

* Baekjoon Online Judge, 백준 2667번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2667번 단지번호붙이기

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

---

2) 풀이 과정

0과 1이 저장되어 있는 2차원 배열 안에서 1이 담긴 곳을 집으로 가정하고 집들이 상하좌우로 연결되어 있는 공간을 단지로 가정했을 때 총 단지의 개수와 각 단지들에 속한 집들의 개수를 출력하는 문제입니다.

 

저의 경우 BFS를 적용해 문제를 해결했으며, 별 특이할 것 없이 완전 탐색을 하다 1이 나오면 BFS를 통해 상하좌우로 연결되어 있는 모든 집들을 찾아주시면 되겠습니다.

---

3) 코드

 

* Python 코드

import sys, queue
input = sys.stdin.readline
 
 
def BFS(i, j):
    global N, house, dx, dy, visit, district
    count = 0
    q = queue.Queue()
    q.put((i, j))
 
    while q.qsize():
        x, y = q.get()
 
        if visit[x][y] == False:
            visit[x][y] = True
            count += 1
            for way in range(4):
                ii, jj = x + dx[way], y + dy[way]
                if ii < 0 or ii > N - 1 or jj < 0 or jj > N - 1:
                    continue
                if house[ii][jj] == 1:
                    q.put((ii, jj))
    district.append(count)
 
 
N = int(input())
house = [list(map(int, input().rstrip())) for _ in range(N)]
dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
visit = [[False] * N for _ in range(N)]
district = []
 
for i in range(N):
    for j in range(N):
        if house[i][j] == 1 and visit[i][j] == False:
            BFS(i, j)
 
print(len(district))
print(*(sorted(district)), sep="\n")

---