[실버 III] 2606번. 바이러스

 문제 

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

2606번: 바이러스

 사용 언어 

Python3

 풀이 과정 

bfs 문제라지만 bfs로 못풀겠어서(이론에서 문제에 적용 어떻게 하는건즤!!!) 내 논리대로 풀었다가 틀렸다. 근데 웬만한건 정답이 떠서 웨!!! 틀린거야!!하고 스터디원들과도 상의했지만 맞을 듯 말듯 계속 틀렸다.

알고보니 문제는 내가 각 숫자에 방문처리를 해서(시작은 bfs였기 때문)

[[1, 2], [2, 3], [3, 4], [5, 6], [7, 8], [8, 9], [9, 1]]
[[1, 2, 3, 4], [5, 6], [7, 8, 9]]
{1: 0, 2: 0, 3: 0, 4: 0, 5: 1, 6: 1, 7: 2, 8: 2, 9: 2}
result: 3
answer: 6

마지막 [9,1]같은 경우는 따로 일을 안하고 저대로 끝내버리는 것...!

그래서 아래 코드를 추가했다.

else: # 둘 다 방문했을 때
            if link_index[i] == link_index[j]: # 같은 리스트에 들어있으면 문제 없음
                continue
            else: # 두 개가 따로 들어가 있으면
                first = min(link_index[i], link_index[j]) # 먼저 들어간 리스트 인덱스 찾기
                later = max(link_index[i], link_index[j]) # 나중에 들어간 리스트 인덱스 찾기
                for num in link_info[later]: # 인덱스 갱신하고
                    link_index[num] = first
                link_info[first] += link_info[later] # 합치기

 

그렇게 9일만에 재시도해서 본 맞았습니다!! 와 근데 생각보다 시간이... 64ms라니 감격😆

python3로 해결하신 분들 보면 7~80ms가 평균인 문제이긴 한데 그래도 만족스럽다 ㅎㅎ(물론 대신 메모리를 왕창 씀)

사실 잊고 있었다가 실패라고 뜨는게 싫어서 재도전했다가 금방 해결했다. 내가 짠 방식 버리기 싫어서 꾸역꾸역 해결했는데 그래도 bfs 방식으로 풀 수 있도록 다른 코드 보고 공부할 것!!! 어쩌다보니 구현 문제처럼 해결해버림;

 제출 답안 

import sys

computer = int(sys.stdin.readline().strip())
pair = int(sys.stdin.readline().strip())
graph = []

for _ in range(pair): # 연결된 컴퓨터 쌍 정보
    graph.append(list(map(int, sys.stdin.readline().split())))

graph.sort(key = lambda x : (x[0], x[1]))
visited = [False] * (computer + 1) # 방문 확인 리스트

def virus(graph, start, visited):
    if (graph[0][0] != 1):
        return 0
        
    link_info = [] # 연결된 그래프 정보
    link_index = {} # 각 숫자가 들어간 그래프의 인덱스

    for i, j in graph: # [1, 2] [2, 3] ... [4, 7]
        if not visited[i] and not visited[j]: # 둘 다 방문하지 않은 상태이면
            visited[i] = True
            visited[j] = True
            link_info.append([i, j]) # 새로운 리스트로 추가
            link_index[i] = len(link_info) - 1
            link_index[j] = len(link_info) - 1
        elif visited[i] and not visited[j]: # i만 방문했으면
            visited[j] = True
            link_info[link_index[i]].append(j) # i가 들어있는 리스트에 추가
            link_index[j] = link_index[i] # 인덱스는 i랑 같음
        elif visited[j] and not visited[i]: # j만 방문했으면
            visited[i] = True
            link_info[link_index[j]].append(i) # j가 들어있는 리스트에 추가
            link_index[i] = link_index[j] # 인덱스는 j랑 같음
        else: # 둘 다 방문했을 때
            if link_index[i] == link_index[j]:
                continue
            else: # 두 개가 따로 들어가 있으면
                first = min(link_index[i], link_index[j]) # 먼저 들어간 리스트 인덱스 찾기
                later = max(link_index[i], link_index[j]) # 나중에 들어간 리스트 인덱스 찾기
                for num in link_info[later]: # 인덱스 갱신하고
                    link_index[num] = first
                link_info[first] += link_info[later] # 먼저 들어간 리스트에 합치기

    return len(link_info[link_index[start]]) - 1 # 바이러스가 시작된 컴퓨터가 속한 리스트의 길이에서 본인 빼기

print(virus(graph, 1, visited)) # 바이러스는 1번 컴퓨터에서 시작됨

 다른 사람 답안 

내 코드에서는 따로 공부한 내용이 없고 다른 사람 답안을 보고 bfs 형식으로 어떻게 풀었어야 하는 건지 공부했다.

마침 어떤 분이 BFS와 DFS 방식까지 비교해주셨길래 바로 참고했다. 감사합니다~!

 

두 코드 모두 52ms가 걸렸다고 언급해주셨고(64ms에 감격할게 아니었구나ㅎㅎ;) 개인적으로 이 문제는 DFS가 이해도 잘되고 깔끔해보였다. 출처 블로그에 설명이 잘 되어 있으니 나중에 복습할 때 참고하면 좋을 것 같다.

 

DFS 코드

from sys import stdin
read = stdin.readline
dic={}
for i in range(int(read())):
    dic[i+1] = set()
for j in range(int(read())):
    a, b = map(int,read().split())
    dic[a].add(b)
    dic[b].add(a)

def dfs(start, dic):
    for i in dic[start]:
        if i not in visited:
            visited.append(i)
            dfs(i, dic)
visited = []
dfs(1, dic)
print(len(visited)-1)

출처: https://chancoding.tistory.com/60

 

BFS 코드

from sys import stdin
read = stdin.readline
dic={}
for i in range(int(read())):
    dic[i+1] = set()
for j in range(int(read())):
    a, b = map(int,read().split())
    dic[a].add(b)
    dic[b].add(a)

def bfs(start, dic):
    queue = [start]
    while queue:
        for i in dic[queue.pop()]:
            if i not in visited:
                visited.append(i)
                queue.append(i)
visited = []
bfs(1, dic)
print(len(visited)-1)

출처: https://chancoding.tistory.com/60

 

두 코드를 각각 VSC로 따라 치면서 공부했는데 처음 보는 문제에 적용할 수 있도록 더 많은 문제를 접해봐야겠다.