2024. 10. 23. 21:26ㆍ카테고리 없음
문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
예제 입력 1
7
6
1 2
2 3
1 5
5 2
5 6
4 7
예제 출력 1
4
풀이
이 문제는 dfs를 이용하여 구현하면 맞을 수 있습니다.
dfs에 대해서는 다음 링크를 확인하시면 됩니다.
일단 서로 노드끼리 서로 연결되어 있는 것을 표시하기 위해서
2차원 리스트 a를 만들어 줍니다.
예시)
a = [[] for _ in range(n+1)] #여기서 n은 노드의 개수 입니다.
그리고 간선의 개수인 k번을 반복해서 입력을 받아 줍니다.
이때 a를 이용하여 노드끼리 서로 연결되어 있는 것을 표시합니다.
예시)
a = [[] for _ in range(n+1)]
for _ in range(k):
u,v = map(int,input().split())
a[u].append(v) # a의 u번째 칸에 k를 더한다.
a[v].append(u)
이때 a가 어떻게 생겼는지 입력 예시를 예로 표기해 보겠습니다.
[]
[2,5] # 1번 노드가 5번 노드와 2번 노드랑 연결 되어 있다.
[1,3,5]
[2]
[7]
[5]
[1,2,6]
[4]
이제 본격 적인 dfs에 들어가기에 앞서, visited에 대해서 알아보겠습니다.
a와 마찬가지로 n+1칸을 가지고 있는 visited는 dfs를 돌 때, 중복으로 한 노드에 가지 않도록 체크를 해주는 배열입니다.
이렇게 방문은 1, 방문하지 않은 노드는 0으로 표기해 무한 루프를 방지할 수 있습니다.
자 이제 dfs를 구현해 보겠습니다.
일단 함수를 정의하는데 필요한 변수는 현재 노드의 값을 나타내는 now입니다.
def dfs(now):
그리고 방문을 했으니 방문 체크를 해야겠죠?
visited[now]를 1로 바꿔 줍니다.
그리고 문제에서 원하는 답은 "몇 개의 노드를 방문했는가?" 이므로 답을 저장할 변수 ans에 1을 더합니다.
아 참! 밖에서 정의한 변수의 값을 변경하려면 global을 사용해 줘야 하니 주의하세요.
예시)
def dfs(now):
global ans # 밖에서 정의한 변수 이므로 global을 붙임
visited[now] = 1 # 방문 체크
ans+=1 #답에 1증가
자 이제 아까 만들었던 a배열에 now번째를 확인해 모든 노드를 꺼내 줍니다.
def dfs(now):
global ans
visited[now] = 1
ans+=1
for new in a[now]:
자 이제, 만약에 visited[new]가 아직 방문 전이라면 재귀를 해주면 dfs는 끝입니다.
마지막 답 출력!
답은 처음 노드를 재외 한 방문한 노드의 개수를 출력해야 하므로, ans-1을 출력해 줍니다.
전체 코드입니다.
def dfs(now):
global ans #외부에서 만든 변수이므로 global을 붙임
visited[now] = 1 #방문 체크
ans+=1 #현재 노드 카운트
for new in a[now]: #연결된 노드 탐색
if visited[new] == 0: #방문이 안됬으면 방문
dfs(new)
n = int(input())
k = int(input())
visited = [0 for _ in range(n+1)] #방문 체크 리스트
a = [[] for _ in range(n+1)]
for _ in range(k):
u,v = map(int,input().split())
a[u].append(v)
a[v].append(u)
ans = 0
dfs(1) #1번부터 탐색
print(ans-1) #처음 노드를 재외한 답 출력
이 블로그를 봐주신 여러분 감사합니다!
