[BAEKJOON/Python] no.2606 바이러스 | DFS/BFS

문제

---

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

2606번: 바이러스

 

1차 풀이

---

computer_count = int(input())
network_count = int(input())

graph = [[] for _ in range(computer_count + 1)]
for i in range(network_count):
    from_com, to_com = map(int, input().split())
    graph[from_com].append(to_com)
    graph[to_com].append(from_com)

strat_com = 1
get_attacked_com = []

for com_num in range(1, computer_count + 1):
    for linked_com in graph[com_num]:
        if linked_com is 0:
            continue
        attecked_index = graph[com_num].index(linked_com)
        parent_index = graph[linked_com].index(com_num)
        if linked_com not in get_attacked_com:
            get_attacked_com.append(linked_com)
            graph[com_num][attecked_index] = 0
            graph[linked_com][parent_index] = 0
        else:
            graph[com_num][attecked_index] = 0
            graph[linked_com][parent_index] = 0
            
print(get_attacked_com)

👉🏻처음에는 일단 graph에 익숙해지고 코드가 어떻게 돌아가는지 파악하려고 무대포로 풀었다.

computer_count = int(input())
network_count = int(input())

graph = [[] for _ in range(computer_count + 1)]
for i in range(network_count):
    from_com, to_com = map(int, input().split())
    graph[from_com].append(to_com)
    graph[to_com].append(from_com)
    
strat_com = 1
get_attacked_com = []

• computer_count에 컴퓨터(노드)의 개수를, network_count에 각 컴퓨터들이 연결된 네트워크(간선)의 개수를 할당했다.
• 이후 for문을 돌리면서 graph의 각 컴퓨터 index에 연결된 컴퓨터들을 넣었다.
• 그리고 start_com에 바이러스 시초인 1번과 바이러스에 전염된 컴퓨터들을 넣기 위해 get_attacked_com라는 리스트를 만들었다.

print(graph)
#[[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]

👉🏻graph를 print하면 다음과 같다. 0번 컴퓨터는 없으므로 아무것도 저장되어 있지 않고 1번은 2, 5번과 연결되어 있어서 숫자 2, 5가 들어있고 마찬가지로 2번은 1, 3, 5번 컴퓨터와 연결되어 있어 숫자 1, 3, 5가 들어있다. 나머지도 이 맥락과 같다.

for com_num in range(1, computer_count + 1):
    for linked_com in graph[com_num]:
        if linked_com is 0: 
            continue
        attecked_index = graph[com_num].index(linked_com)
        parent_index = graph[linked_com].index(com_num)
        if linked_com not in get_attacked_com:
            get_attacked_com.append(linked_com)
            graph[com_num][attecked_index] = 0
            graph[linked_com][parent_index] = 0
        else:
            graph[com_num][attecked_index] = 0
            graph[linked_com][parent_index] = 0

• 1부터 computer_count + 1까지 for문을 돌리며 graph의 각 컴퓨터 인덱스(com_num)를 확인한다.
• graph에 담긴 각 컴퓨터에 연결된 컴퓨터들(linked_com)을 이중 for문을 돌리면서 확인한다.
  • linked_com이 get_attacked_com에 포함되어 있지 않다면 get_attacked_com에 추가하고 graph에서 linked_com에서 com_num을 0으로 바꿔준다. 그리고 graph에서 com_num에서 linked_com을 0으로 바꿔준다.
  • liked_com이 get_attacked_com에 포함되어있다면 추가하지 않고 0으로 바꿔준다.
  • 만약 linked_com이 0이면 이미 확인한 컴퓨터이기 때문에 continue를 한다.
    • 만약 이 작업을 하지 않으면 graph의 0번째 인덱스에 아무 값도 없기 때문에 오류가 발생한다.

👉🏻이미 확인했던 컴퓨터들을 표시하려는 목적으로 0으로 바꾸었다.

 

💡 내가 기억하려고 적어두는 continue와 break와 pass

continue	for문을 돌릴 때 해당 forloop 하나만 건너뛴다.
break	for문을 돌릴 때 해당 for문 자체를 건너뛴다.
pass	for문 상관없이 아래 코드를 계속 진행한다.

 

for com_num in range(1, computer_count + 1):
    for linked_com in graph[com_num]:
        if linked_com is 0: 
            continue
        attecked_index = graph[com_num].index(linked_com)
        parent_index = graph[linked_com].index(com_num)
        if linked_com not in get_attacked_com:
            get_attacked_com.append(linked_com)
            graph[com_num][attecked_index] = 0
            graph[linked_com][parent_index] = 0
            print('this com is ', com_num, 'linked com is ',linked_com,)
            print(linked_com, 'is not attacked')
            print('the graph is ',graph, 'attacked is ', get_attacked_com)
            print('-----')
        else:
            graph[com_num][attecked_index] = 0
            graph[linked_com][parent_index] = 0
            print('this com is ', com_num, 'linked com is ',linked_com,)
            print(linked_com, 'is attacked')
            print('the graph is ',graph, 'attacked is ', get_attacked_com)
            print('-----')

👉🏻이러한 형태로 출력해보았다.

👉🏻문제점은 아래와 같다. 

1. 연결된 컴퓨터를 제대로 파악하지 않는 점. 
   • 과정 도중 graph의 3번 인덱스의 값이 [0]이기 때문에 그냥 넘어간다.
2. 연결되어 있지 않은 컴퓨터들도 확인을 한다는 점.
   • 4번 컴퓨터는 확인할 필요가 없는데 확인하고 있다.

 

2차 풀이 : DFS 활용

---

위의 문제점을 해결하기 위해 DFS의 재귀방식으로 풀이를 진행했다! 

computer_count = int(input())
network_count = int(input())

graph = [[] for _ in range(computer_count + 1)]
for i in range(network_count):
    from_com, to_com = map(int, input().split())
    graph[from_com].append(to_com)
    graph[to_com].append(from_com)

start_com = 1
linked_with_start_com = []

def dfs(com_num):
    linked_com_list = []
    for linked_com in graph[com_num]:
        if linked_com is 1 or linked_com in linked_with_start_com:
            continue
        else:
            linked_with_start_com.append(linked_com)
            linked_com_list.append(linked_com)
    
    for com in linked_com_list:
        dfs(com)

dfs(start_com)

print(len(linked_with_start_com))

👉🏻전체 소스코드이다. 한 줄씩 뜯어보자!

linked_with_start_com = []

👉🏻초기 세팅에서 바뀐 점은 get_attacked_com이 linked_with_start_com으로 이름이 바뀐 것 말고는 없다.

def dfs(com_num):
    linked_com_list = []
    for linked_com in graph[com_num]:
        if linked_com is 1 or linked_com in linked_with_start_com:
            continue
        else:
            linked_with_start_com.append(linked_com)
            linked_com_list.append(linked_com)
    
    for com in linked_com_list:
        dfs(com)

• 받은 컴퓨터 번호를 graph에서 찾아(linked_com) for문을 돌린다.
  • 만약 linked_com이 1이면 시작 컴퓨터이므로 continue한다.
  • 혹은 linked_with_start_com에 있다면 이미 탐색한 컴퓨터이므로 continue한다.
  • 그렇지 않으면 linked_with_start_com과 linked_com_list에 추가한다.
• linked_com_list를 for문에 돌리면서 다시 dfs를 호출한다.

👉🏻여기서 linked_with_start_com리스트를 사용하면 무한 루프에 빠지게 된다. 무한 루프를 피하기 위해 dfs내에서만 사용하는 linked_com_list를 사용해야 한다.

👉🏻dfs를 재귀적으로 호출하면서 위의 두 가지 문제점을 동시에 해결할 수 있었다!

def dfs(com_num):
    linked_com_list = []
    for linked_com in graph[com_num]:
        if linked_com is start_com or linked_com in linked_with_start_com:
            continue
        else:
            linked_with_start_com.append(linked_com)
            linked_com_list.append(linked_com)
    print('this com is ', com_num)
    print('linked_with_start_com is ', linked_with_start_com)
    
    for com in linked_com_list:
        dfs(com)

👉🏻위와 같이 print를 찍어보니 다음과 같이 나왔다.

👉🏻코드 잘 돌아가고 있음!

한 번에 맞음 아싸!