BOJ:ウイルス[2606]

10096 ワード
テキストリンク

1.質問


新型ウイルスワームウイルスはネットワークを通じて伝播する.1台のコンピュータがワームウイルスに感染した場合、ネットワークに接続されているすべてのコンピュータがワームウイルスに感染します.
例えば、<図1>に示すように、7台のコンピュータがネットワークに接続されているとする.1番のコンピューターがワームウイルスに感染した場合、ワームウイルスは2番と5番のコンピューターを経て3番と6番のコンピューターに伝播し、2、3、5、6の4台のコンピューターがワームウイルスに感染する.しかし、4番と7番は1番とネットワーク接続がないため、影響を受けません.

ある日、1番のパソコンがワームウイルスに感染した.コンピュータの数とネットワーク上の情報が相互に接続されている場合は、コンピュータを介してワームウイルスに感染したコンピュータの数を出力するプログラムを作成します.
ソース:https://www.acmicpc.net/problem/2606

2.アイデア

  • mine
  • DFSでアクセスチェックを行い、1番のコンピュータを除外するのでアクセス数を計算して-1を行います.
    • clone
  • DFSアクセスを使用する場合にのみ追加されるポイントとsortではなくdictionaryおよびsetを使用するポイントは異なります.

    • 3.コード


    mine
    import sys
input = sys.stdin.readline

def dfs(graph, v, visited):
  #현재 노드를 방문 처리
  visited[v] = True
  #현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)

computer = int(input())
connected_pair = int(input())

graph = [[] for _ in range(computer+1)]

for _ in range(connected_pair):
    x,y=map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

for g in graph:
    g.sort()

visited = [False] * (computer+1)
dfs(graph, 1, visited)
print(visited.count(True)-1)
    clone
    from sys import stdin
read = stdin.readline
dic={}
for i in range(int(read())):
    dic[i+1] = set()
for j in range(int(read())):
    a, b = map(int,read().split())
    dic[a].add(b)
    dic[b].add(a)

def dfs(start, dic):
    for i in dic[start]:
        if i not in visited:
            visited.append(i)
            dfs(i, dic)
visited = []
dfs(1, dic)
print(len(visited)-1)
    ソース:https://chancoding.tistory.com/60

    4.比較結果


    1. mine

    2. clone
    [SPRING]スプリング入門コース-スプリングWeb開発基礎
    Codekata #3