백준 2606, 11724

2606 바이러스

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

'''
input = 
    7		=> 컴퓨터의 수 
    6
    1 2
    2 3
    1 5
    5 2
    5 6
    4 7

output = 
	4
'''

n = int(input()) # 정점 개수(컴퓨터)
m = int(input()) # 간선 개수(네트워크)
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)             # 방문 여부 확인 리스트 생성

for _ in range(m):
    v1, v2 = map(int, input().split())	# 노드값 넣어주기
    graph[v1].append(v2)
    graph[v2].append(v1)

# 인접 노드 탐색
def dfs(start):
    stack = [start]                     # 1번 노드부터 시작하기 위해 적어준 구문. 이후 이 구문으로 오지 않는다.                 
    visited[start] = True               # 1번 노드를 True로 바꿔준다. 

    while stack:                        # while len(stack) != 0: 스택이 비워있을 때 멈춘다.
        current = stack.pop()           # 스택에서 빠진 노드값이 current에 들어간다.

        for adj in graph[current]:      # 빠진 노드가 인접 리스트 상에 포함된(연결된) 다른 노드 값을 adj에 하나씩 넣어준다.
            if not visited[adj]:        # 인접한 노드를 방문하지 않았다면
                visited[adj] = True     # True로 바꿔준다. 
                stack.append(adj)       # 해당 노드값을 stack에 넣어준다. 
dfs(1)                                  # 1번 노드부터 시작하게 해준다. 

print(visited.count(True) - 1)          # 맨 처음 시작했던 1번 노드는 빼준다.

1과 연결된 노드의 개수를 구한다. 

위의 코드에서 input 값을 나타내 보자면, 

 

2, 3, 5, 6 의 노드는 모두 1과 연결되어 있으며, 4와 7은 동떨어져 있는 상태이다. 

즉, 1과 연결된 노드의 수는 2, 3, 5, 6이므로 출력값은 4가 된다. 

graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)             # 방문 여부 확인 리스트 생성

인접 리스트인 노드의 값들을 넣어줄 graph를 만들고, 

방문 여부를 확인할 visited 리스트를 만들어준다. 방문 할 경우 True, 방문하지 않을 경우 False를 나타낸다. 

입력값에 따라 1에 인접한 노드인 1을 포함한 2, 3, 5, 6은 visited의 값이 True로 바뀔 것이고, 인접하지 않은 노드 4, 7은 False로 남을 것이다. 

 

for _ in range(m):
    v1, v2 = map(int, input().split())	# 노드값 넣어주기
    graph[v1].append(v2)
    graph[v2].append(v1)

노드값인 입력값을 graph에 넣어준다.

입력값이 1 2 일 경우, 인덱스 1 위치에는 2와 동시에 인덱스 2 위치에 1이 들어가게 된다. 

 

# 인접 노드 탐색
def dfs(start):
    stack = [start]                     # 1번 노드부터 시작하기 위해 적어준 구문. 이후 이 구문으로 오지 않는다.                 
    visited[start] = True               # 1번 노드를 True로 바꿔준다. 

    while stack:                        # while len(stack) != 0: 스택이 비워있을 때 멈춘다.
        current = stack.pop()           # 스택에서 빠진 노드값이 current에 들어간다.

        for adj in graph[current]:      # 빠진 노드가 인접 리스트 상에 포함된(연결된) 다른 노드 값을 adj에 하나씩 넣어준다.
            if not visited[adj]:        # 인접한 노드를 방문하지 않았다면
                visited[adj] = True     # True로 바꿔준다. 
                stack.append(adj)       # 해당 노드값을 stack에 넣어준다. 
dfs(1)                                  # 1번 노드부터 시작하게 해준다.

dfs 함수 하단의 'dfs(1)'로 인해 start 값은 1이 되며,  노드 1부터 탐색을 시작한다.

구문 차례대로 stack에 1이 들어가게 되고, visited 리스트의 인덱스 1 위치의 값은 True로 바뀌게 된다.

 

'while stack:'은 'while len(stack) != 0'와 같은 구문으로, stack에 값이 없을 때까지 반복문을 진행한다. 

 

stack에 있는 값을 제거함과 동시에 제거된 값은 current 변수에 들어감으로써, 이후 for문에서 제거된 값(current 값)으로 이동하여 노드들을 탐색하게 된다. 

 

current의 값이 1일 때 graph[current]는 graph[1]이 되므로, graph의 인덱스 1의 위치에 들어가 있는 값을 adj에 하나씩 넣어준다. 즉, 노드 1에 인접한 노드로 이동하는 것이다. 

이동한 노드가 2일 때 방문한 적이 없다면 visited 리스트의 인덱스 2의 위치 값인 False를 True로 바꿔준다. 

이후 2는 stack에 삽입된다. 

 

이 과정을 stack에 값이 없을 때까지 반복한다면 1에 인접한 노드들을 모두 방문하게 된다. 

print(visited.count(True) - 1)          # 맨 처음 시작했던 1번 노드는 빼준다.

방문한 노드들은 visited 리스트에서 모두 True로 바뀌게 된다. 

이를 통해 바이러스에 걸린 컴퓨터의 수를 True 값의 수를 세어 출력하도록 한다. 이때 1은 포함하지 않아야 하므로 1을 뺀다. 

 

11724 연결 요소의 개수

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

'''
input = 
6 5
1 2
2 5
5 1
3 4
4 6

output = 
2

'''

n, m = map(int, input().split())        # 정점 개수(컴퓨터), 간선 개수(네트워크) 입력 
graph = [[] for _ in range(n + 1)]      # 인접 리스트를 넣어줄 리스트 생성
visited = [False] * (n + 1)             # 방문 여부 확인 리스트 생성

for _ in range(m):
    v1, v2 = map(int, input().split())  # 노드값 넣어주기
    graph[v1].append(v2)
    graph[v2].append(v1)

# 인접 노드 탐색
def dfs(start):
    stack = [start]                     # 1번 노드부터 시작하기 위해 적어준 구문. 이후 이 구문으로 오지 않는다.                 
    visited[start] = True               # 1번 노드를 True로 바꿔준다. 

    while stack:                        # while len(stack) != 0: 스택이 비워있을 때 멈춘다.
        current = stack.pop()           # 스택에서 빠진 노드값이 current에 들어간다. 즉, 노드를 이동하는 역할이 된다.

        for adj in graph[current]:      # stack에서 제거된 노드값이 graph의 인덱스 위치가 된다. 인접 리스트 상에 포함된(연결된) 다른 노드 값을 adj에 하나씩 넣어준다.
            if not visited[adj]:        # 인접한 노드를 방문하지 않았다면
                visited[adj] = True     # True로 바꿔준다. 
                stack.append(adj)       # 해당 노드값을 stack에 넣어준다. 

cnt = 0
for i in range(1, n + 1):               # start 설정
    if not visited[i]:                  # 만약 방문기록 리스트의 i번째가 True가 아니라면
        dfs(i)                          # i로 이동한다.
        cnt += 1                        # dfs에서 연결된 노드를 모두 탐색한 후 이 구문으로 돌아와 cnt에 +1 
print(cnt)

내가 생각한 '연결 요소'는 노드들이 서로 연결된 덩어리?,,의 개수이며, 이를 출력한다고 생각했다. 

노드들이 연결된 한 묶음을 출력하기 위해 위 바이러스의 문제 풀이 코드에서 for문을 추가하였다.

 

시작하고자 하는 노드를 for문으로 설정하여 연결되지 않은 노드 묶음으로 넘어가도록 한다. 

1부터 시작하여 while 반복문을 통해 연결된 노드들인 2, 5를 방문하게 된다. 

한 묶음의 방문이 끝나면 다시 하단의 for문으로 돌아와 방문하지 않은 노드를 탐색한다. 다시 for문으로 돌아올 때 cnt에 1을 더해서 한 묶음의 개수를 세준다. 

이후 i 값이 3이 될 때 visited[3]의 값은 False이므로 dfs(3)이 되어 다시 노드 3에 인접한 노드를 탐색하기 위해 while문을 반복하게 된다.