[Baekjoon][Python]2606号ウイルス

7869 ワード
baekjoon テキストリンク
2606号ウイルス

質問する



に答える


この問題はDFSで解決できる.
グラフを実装するためにグラフというクラスを自分で作成しました.
Pythonではディック・シャナリーとリストで隣接リストを容易に実現できる.
問題をよく観察する場合は、すべてのグラフィックを作成した後、1番ノードからDFSナビゲーションを行い、アクセスなしでcountを増やすだけです.countは感染したパソコンの数です.最初は1番ノードにアクセスするので、出力時には-1しか必要ありません.
コードは次のとおりです.
import sys

class Graph:
    def __init__(self):
        self.graph = {}
    def addVertex(self, vertex):
        self.graph[vertex] = []
    def addEdge(self, startVertex, endVertex):
        self.graph[startVertex].append(endVertex)

def searchInfection(graph, startVertex, visited, count):
    visited[startVertex] = 1
    count += 1
    for s in graph.graph[startVertex]:
        if visited[s] != 1:
            visited, count = searchInfection(graph, s, visited, count)
    return visited, count
            
# 컴퓨터의 수
N = int(sys.stdin.readline())

# 그래프 선언
cGrpah = Graph()
visited = []

# vertex 추가
for i in range(N):
    cGrpah.addVertex(i + 1)
    visited.append(0)
visited.append(0)

# 연결된 컴퓨터 쌍 수
M = int(sys.stdin.readline())

# edge 추가
for i in range(M):
    c1, c2 = map(int, sys.stdin.readline().split())
    cGrpah.addEdge(c1, c2)
    cGrpah.addEdge(c2, c1)
    
# 검색
count = 0
visited, count = searchInfection(cGrpah, 1, visited, count)


# 방문한 노드 개수
print(count - 1)

n/a.結論


今回の問題はDFSアルゴリズムを使って、概念を勉強すれば、いろいろな面でうまく使えるということです.Pythonでグラフを実現することに慣れていないため、コードの整理はあまりはっきりしていませんが、今後のコードでは、より簡潔なコードを書くことができるはずです.
[PROGRAMMERS]救命ボート(レベル2)
redux thunk