0319 TIL

looggi·2023년 3월 19일

TILs

목록 보기

40/114

스터디 문제 풀기

➡️ 바이러스

import sys

t=int(input()) #컴퓨터의 수
num=int(input())
ans=[]
for i in range(num):
    p=sys.stdin.readline() # 컴퓨터의 번호 쌍
    from_p,to_p=p.split()
    if from_p=='1' or (from_p in ans):
        ans.append(to_p)       
print(len(set(ans)))

처음에 이렇게 코드를 짰는데 이러면 마지막에 새롭게 연결되는 컴퓨터가 나오면 그 컴퓨터로 인해서 감염되는 컴퓨터를 찾을 수 없다는 문제가 생긴다....... 반복문 여러번 돌리면 되야하는거 아닌가 진짜 인정할 수 없어...라고 생각했지만 예제는 컴퓨터의 수도 적고 네트워크도 복잡하지 않았어서 정답처리가 됐지만 컴퓨터의 수가 많아지고 네트워크가 복잡해지면 네트워크가 얼마나 깊어지는지에 따라서 누락되는 컴퓨터가 생길 수 있어서

DFS로 푸는 게 맞다

computer = int(input())
pairs = int(input())
graph = [[] for _ in range(computer+1)]
visited = [0] * (computer + 1)
for _ in range(pairs):
    from_p, to_p = map(int, input().split())
    graph[from_p].append(to_p)
    graph[to_p].append(from_p)
    
visited[1] = 1 # 1번 컴퓨터 감염
stack = [1]
v=1
while stack:
    for w in graph[v]:
        if visited[w] == 0:
            visited[w] = 1
            stack.append(v)
            v = w
            break
    else:
        v = stack.pop()
            
print(sum(visited)-1)

컴퓨터의 수를 입력받고, 입력받는 컴퓨터 쌍의 수를 입력받는다
인덱스 = 컴퓨터 번호로 각 컴퓨터에 연결된 컴퓨터들을 입력할 그래프를 만든다
컴퓨터 쌍의 수만큼 연결된 컴퓨터 쌍들을 입력 받아서 양방향으로 연결해준다(=각 인덱스에 넣어주는 것)

visited는 인덱스 번호에 해당하는 컴퓨터가 감염되었는지를 표시한다

1번 컴퓨터가 감염되었으므로 visited의 1번 인덱스에 1을 넣어준다

graph[1]의 요소w들은 1번 컴퓨터와 연결된 컴퓨터들이고 그 컴퓨터들이 감염되어있지 않다고 표시되어있으면(0값) 1로 바꿔주고 stack에 append해서 기록해둔다
stack에 들어간 컴퓨터들은 이전에 연결되었던 컴퓨터를 기록해서 for문에서 graph[v]에 있는 컴퓨터들이 모두 감염 표시가 된 경우 else문에서 연결된 모든 컴퓨터에 대해 감염 표시를 할 수 있게 해준다- 애초에 1번과 연결되지 않은 컴퓨터는 graph[v]의 v에 들어갈 수가 없기때문에 모든 0은 1로 바뀌어야 맞음