[백준] 2667번, 단지번호붙이기 (Python)

문제

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

2667번: 단지번호붙이기

 

코드

import collections

n = int(input())
graph = [list(map(int,input().strip())) for _ in range(n)]
check = [[False]*n for _ in range(n)]

def bfs(x,y):
    count = 1
    check[x][y] = True
    queue = collections.deque()
    queue.append((x,y))
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] == 1 and check[nx][ny] == False:
                    count += 1
                    check[nx][ny] = True
                    queue.append((nx,ny))
    return count

result = []
for x in range(n):
    for y in range(n):
        if graph[x][y] == 1 and check[x][y] == False:
            result.append(bfs(x,y))

# 총 몇개의 단지가 있는지 계산해준다.
print(len(result))
result.sort()
for i in result:
    print(i)

총 몇개의 단지가 있는지랑 단지내의 가구수를 오름차순으로 출력하는 문제이다.

 

graph와 check 리스트를 통해 입력을 받은다음 2중 for문을 돌아 graph값이 1이고 check가 False인 경우에 bfs함수를 실행시켜준다.

서로연결된 1같은 경우는 모두 check가 True 바뀌기 때문에 bfs함수 실행 수 즉 result 리스트에 길이가 단지의 개수가 된다.

 

단지내의 가구수는 처음에 1로 시작하는데 왜냐하면 bfs(x,y)가 실행되었다는 얘기는 x,y는 1인것이 확정이기 때문에 count는 1부터 세어주면된다.

 

graph값이 1이고 check가 False인 경우에는 처음 접근한 1이기때문에 count +1해준다음에 queue를 모두 돌고나면 count를 리턴해주면된다.