[BOJ 2667]番号のみ(Python)


質問する


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

問題は、接続された家屋の団地数を出力し、昇順に各団地に属する家屋数を出力することである.
問題はよく読めず、以前の問題と同じように挿入しました.⛏

問題を解く

  • アクセス関数は単独で作成されず、一度にアクセスした家は値を0に変更して再アクセスを回避します.
  • 現在座標(i,j)が家であればcntを1、現在座標を非家(0)とする.
  • キューに(i,j)を入れます.
  • (i,j)の上下左右が家であれば,(nx,ny)をキューに入れ,cntに1を加える.
    同様に,(nx,ny)を非家(0)にする.
  • に接続されているすべての場所を確認し、キューが空の場合、回答リストにcntを追加します.
    このときcntは各団地に属する家数である.
  • 解答リストの長さは園区の数であり,解答の要素は各園区に属する家の数である.
  • コード#コード#

    N = int(input())
    li = [list(input().rstrip()) for _ in range(N)]
    
    ans = []
    dx = [1,-1,0,0]
    dy = [0,0,-1,1]
    
    for i in range(N):
        for j in range(N):
            if li[i][j] == "1":
                cnt = 1
                li[i][j] = "0"
                q = [(i,j)]
                while q:
                    x,y = q.pop(0)
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if 0 <= nx < N and 0 <= ny < N:
                            if li[nx][ny] == "1":
                                q.append((nx,ny))
                                li[nx][ny] = "0"
                                cnt += 1
                ans.append(cnt)
    ans.sort()       
    print(len(ans))
    for i in ans:
        print(i)