장애물 인식 프로그램

풀이

특징이라면은... visited 배열을 생성하지 않고 graph를 수정하며 중복 방지를 했다. 우리는 1을 지나다니며 탐색을 하기 원하기 때문에 이미 방문한 지점을 0으로 수정하여 재방문 하지 않게 설계했다.

초기 조건

• n: 그래프의 가로/세로 길이
• graph: 2차원 행렬, 1은 장애물 0은 길을 의미

최종 문제

• block_num: 1로 이루어진 네트워크의 개수
• one_num: 각 네트워크에 속한 1의 개수

중간 조건/문제

• i,j: BFS 탐색 출발 지점 i는 행 j는 열을 의미
• cnt: BFS 탐색 종료시 방문한 노드의 총 개수
• block_list: 네트워크에 속한 1의 개수를 모아놓은 리스트

사용 함수 및 알고리즘

• BFS: BFS 알고리즘
• append: list의 추가 메서드
• sort: list의 정렬 메서드
• len: list의 길이를 반환해주는 메서드
• for: 반복문

코드

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

def bfs(graph,i,j,n):
    cnt = 1
    q = deque([(i,j)])
    graph[i][j] = 0
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while q:
        x,y = q.popleft()
        for k in range(4):
            nx = x+dx[k]
            ny = y+dy[k]

            if 0<=nx<n and 0<=ny<n and graph[nx][ny]:
                q.append((nx,ny))
                graph[nx][ny] = 0
                cnt += 1
    return cnt,graph

n = int(input())
graph = [[0]*n for _ in range(n)]
for i in range(n):
    temp = input()
    for j in range(n):
        if int(temp[j]):
            graph[i][j] = 1

block_list = list()
for i in range(n):
    for j in range(n):
        if graph[i][j]:
            cnt, graph = bfs(graph,i,j,n)
            block_list.append(cnt)
block_list = sorted(block_list)

block_num = len(block_list)
print(block_num)
for i in range(block_num):
    one_num = block_list[i]
    print(one_num)