백준 2667번 단지번호붙이기 파이썬

리뷰

얼추 BFS에 대해 감이 잡혀 가는 것 같다, 물론 아직 실버 문제지만..

 

문제 풀이

1. 집 정보가 있는 2차원 배열, 방문 여부를 체크할 2차원 배열, 상하좌우를 방문할 방향 배열을 초기화 해준다.
2. 정답을 담을 빈 리스트와 2차원 배열을 탐색할 2중 FOR문을 개행해 준다.
3. 만약 배열 탐색 중 2차원 배열의 값이 1이고 방문 기록이 없다면 해당 좌표를 기준으로 bfs를 실행해 준다.
4. 함수 호출 시 단지 내 집의 개수는 1개이고 bfs실행 중 큐에 인자가 들어갈 때마다 1개씩 더해준다.
5. 각 단지마다 집의 개수를 출력해 준 후 리스트로 저장한다. 최종적으로 리스트의 길이와 요소를 정렬 후 출력

 

 

참고 사항

오름 차순으로 출려기익 때문에 꼭 정렬을 해줘야 한다.

 

 

정답 코드

def q2667():
    # 백준 2667번 단지번호붙이기 파이썬
    from collections import deque

    n = int(input())
    lst = [list(map(int, list(input()))) for _ in range(n)]
    v = [[0] * n for _ in range(n)]
    dist = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def bfs(graph, start, c):
        q = deque([start])
        v[start[0]][start[1]] = True
        while q:
            x, y = q.popleft()
            for dx, dy in dist:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] and not v[nx][ny]:
                    v[nx][ny] = True
                    c += 1
                    q.append((nx, ny))
        return c

    cnt = []
    for i in range(n):
        for j in range(n):
            if lst[i][j] == 1 and v[i][j] == 0:
                cnt.append(bfs(lst, (i, j), 1))
    cnt.sort()
    print(len(cnt))
    for i in cnt:
        print(i)
q2667()