BOJ-2606ウイルス(Python)

質問元:https://www.acmicpc.net/problem/2606

難易度

Silver 3

問題を解く

単純なグラフィックナビゲーションの問題

パスコード

if __name__ == '__main__':
    n = int(input())
    pair = int(input())
    arr = [[0 for x in range(n+1)] for y in range(n+1)]
    ch = list()
    queue = list()
    for i in range(pair):
        x,y = map(int, input().split())
        arr[x][y] = 1
        arr[y][x] = 1
    queue.append(1)
    ch.append(1)
    while queue:
        node = queue.pop(0)
        for i in range(1,n+1):
            if arr[node][i] == 0 or i in ch:
                continue

            queue.append(i)
            ch.append(i)

    print(len(ch)-1)

フィードバック

2次元配列宣言に時間がかかり,最初は[[0]*n]*nであったが,同じ配列n回,(1,2)が1の場合,他の行や列が1でなければならない箇所も1となった.宣言は気をつけて