백준 2606 바이러스

문제 : https://www.acmicpc.net/problem/2606

그냥 그래프 연결해서 순회하면 되는문제

진짜 딱 그게 전부다.

 

인접리스트, 인접행렬

문제에서 신경쓰이는 조건이 있었는데, 메모리제한이 128이다

인접리스트 방식은 ‘연결된 지점'만을 가지고 있고, 인접행렬은 [0,0,0,1,1] 이런식으로 모든 지점에 대한 연결여부를 가지고있는데

주어지는 컴퓨터의 수가 100개니까, 이를 인접행렬 방식으로 구현하게되면 100*100 matrix에 접근해야되는거니까 하면 안되나? 싶었다

 

근데 생각해보니까, 굳이 인접리스트나 인접행렬 상관없이 해도 겨우 10000칸이고, 한칸에 4바이트 잡아도 4만이다. 굳이 메모리 터지는건 신경안써도 될것같다

 

소스코드(전체)

node = int(input())
edge = int(input())
graph = [[] for _ in range(node +1)]
visited = [False] * len(graph)

for q in range(edge) :
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

#print(graph)

count = 0
def dfs(graph, v, visited) :
    visited[v] = True
    global count
    count +=1 

    for i in graph[v] :
        if not visited[i] :
            dfs(graph,i,visited)
dfs(graph,1,visited)
print(count-1)