[백준] 바이러스 2606번

 

 

처음으로 블로그에서 백준 문제를 포스팅하려고 마음먹었을 때, 백준 문제를 풀 때의 경험이 다시 떠올랐습니다. 예전에는 주로 프로그래머스 문제만 푸는 경향이 있었기 때문에, 백준에서 문제를 풀 때는 입력값을 `readLine()`을 사용해 받고 값을 활용하는 것이 쉽지 않았습니다. 때로는 어떻게 해야 할지 막막한 순간도 있었습니다.

하지만 지금까지의 경험을 통해 이 부분에 점점 익숙해지는 것이 중요하다는 것을 알게 되었습니다. 다양한 문제를 풀어보면서 처음부터 효율적이고 Swift 언어의 강점을 살릴 수 있는 방법에 대해 고민하게 되었습니다.

그래서 문제 풀이를 준비하면서 백준과 프로그래머스 문제를 번갈아가며 풀어보고 있다 보니 실력이 점차적으로 늘어나고 있다는 느낌을 받았습니다. 이러한 경험을 바탕으로 블로그에 백준 문제를 다루는 포스팅을 작성하려고 합니다. 😁
앞으로도 계속해서 다양한 문제를 도전하며 실력을 향상시킬 예정이며 💪  블로그를 통해 다른 사람들과 경험을 공유하는 것도 좋은 방법이라고 생각합니다.

 

---

1. 문제 링크 

2606번: 바이러스

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

 

문제

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

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다

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

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

 

예제 입력

7
6
1 2
2 3
1 5
5 2
5 6
4 7

정답 : 4

 

2. 코드

let count = Int(readLine()!)!	//첫 번째 줄은 컴퓨터의 수 
let pairs = Int(readLine()!)!	//둘째 줄은 컴퓨터 쌍의 수

var graph : [Int : [Int]] = [:]

for i in 0..<pairs{	// for in 문을 이용하여 입력받는 pairs 수만큼 반복을 돌려 다른 값들을 받아주기
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }	// 공백 기준 잘라 배열 만들기
    let key = input[0]
    let value = input[1]
    
    // 양 방향 둘다 넣기
    if var temp = graph[key] {
        temp.append(value)
        graph[key] = temp
    } else {
        graph[key] = [value]
    }

    if var temp = graph[value] {
        temp.append(key)
        graph[value] = temp
    } else {
        graph[value] = [key]
    }
    
}

print(bfs(graph: graph))

func bfs(graph: [Int: [Int]]) -> Int{

    // 중복 방지
    var visited = Set<Int>()
    
    var queue = [1]
    visited.insert(1)   // 미리 넣기
    
    while !queue.isEmpty{
        let currentNode = queue.removeFirst()   // 탐색할 노드 빼기 큐 첫 번째에서
        
        if let temp = graph[currentNode] {  // 현재 탐색하는 노드 인접 노드들 탐색
            for node in temp{               // 인접 노드들 중에서 방문한 노드 있는지 확인
                if visited.contains(node){
                    continue
                }
                visited.insert(node)        // 없으면 방문하고 큐에 대기 시키기
                queue.append(node)
            }
        }

    }

    return visited.count - 1
}

 

3. 코드 설명

코딩 테스트를 준비하면서 BFS 관련 문제를 처음으로 접하게 된 문제였습니다. 😅
그래프 관련해서는 더욱 공부하고 정리를 한 다음에 블로그에 다른 카테고리에 포스팅해야 할 거 같습니다ㅋㅋ

// 1번
if var temp = graph[key] {
    temp.append(value)
    graph[key] = temp
} else {
    graph[key] = [value]
}

// 2번
if var temp = graph[value] {
    temp.append(key)
    graph[value] = temp
} else {
    graph[value] = [key]
}

이 부분은 제가 처음 문제를 풀 때 실수한 부분입니다. 처음에는 1번 코드만 작성하고 2번 코드를 작성하지 않았습니다.

그래서 그래프의 방향성에 대해 제대로 깨닫지 못했습니다.
1번과 2번을 간단히 해석하자면

var graph: [Int: [Int]] = [:]

위 코드에서 제가 만든 그래프의 구조는 딕셔너리 형태로 되어 있으며, key 값은 Int 형이고 / value 값은 [Int] 배열로 구성되어 있습니다. 이렇게 만든 이유는 1번 컴퓨터가 여러 개의 다른 컴퓨터와 연결될 수 있기 때문에 [Int]를 만들어 1번 컴퓨터와 연결되어 있는 컴퓨터들의 값들을 저장하려고 했습니다.

1번 코드에서의 if var temp = graph[key] 부분은 반복문을 돌면서 graph[key] 값이 있다면 그 값을 임시로 temp 값으로 가져와 새로운 값인 value를 append하여 다시 해당하는 graph[key] 값에 넣어주는 것입니다.
만약 graph[key]이 없다면 그대로 graph[key] = [value] 값을 넣어 다음 순서로 넘어갑니다.

지금 이 과정을 1번 코드만 살린다면 이 그래프의 방향은 단방향입니다.

여기서 제 실수가 나왔습니다. 문제에서는 네트워크 상에서 연결되어 있는 모든 컴퓨터가 웜 바이러스에 걸리기 때문에

1 -> 2 관계라면 2 -> 1 도 당연히 연결되어 있어야 합니다. 하지만 1번만 살릴 경우에는 연결이 끊겨 있어서 절대적???!으로 정답을 맞히지 못합니다.
그래서 2번 코드를 추가하는 이유는 양방향 그래프로 만들기 위해서입니다. key와 value의 값의 위치를 바꿔서 저장해 줌으로써 양방향 관계를 표현하였습니다.

 

주어진 코드에서는 BFS를 활용하여 그래프를 탐색하는 과정을 구현하였습니다.

1. 반복문을 통해 그래프를 구성한 후, bfs 메서드에 그래프를 전달합니다.

2. 방문한 노드들을 저장하기 위해 visited라는 Set을 생성합니다. 이 Set은 방문한 노드들의 값을 저장하여 방문 여부를 확인하는 데 사용됩니다.

3. Queue인 queue 배열을 생성하여 시작점으로 1을 넣습니다. 문제에서 1번 컴퓨터가 웜 바이러스에 걸렸다고 되어 있기 때문입니다. 또한 방문한 노드를 체크하기 위해 visited에도 초기에 1을 넣어줍니다.

4. while 문을 통해 Queue가 비어있지 않을 때까지 반복합니다. 여기서 Queue는 FIFO(First-In, First-Out)의 개념을 활용합니다. 즉, 먼저 들어온 노드부터 차례대로 탐색합니다.

5. 반복문 안에서는 Queue에서 현재 노드 값을 꺼내고, 해당 노드와 연결된 다른 노드들을 확인합니다. 이때, 전달받은 그래프인 graph에서 현재 노드의 값을 key로 가지는 배열을 가져옵니다.

6. 가져온 배열을 for-in 반복문을 통해 차례대로 확인합니다. 만약 현재 확인하는 노드가 이미 visited 에 포함되어 있다면 다음 요소로 넘어갑니다. 이미 방문한 노드이므로 다른 작업을 할 필요가 없습니다. 그렇지 않은 경우에는 해당 노드를 queue 에 넣고, visited 에도 값을 넣어줍니다. 이렇게 함으로써 감염된 컴퓨터와 연결된 컴퓨터들을 탐색할 수 있습니다.

7. 연결된 컴퓨터가 계속 있다면 while 문은 계속 반복하게 되고, visited에는 감염된 컴퓨터들의 값들이 저장됩니다.

8. while문을 모두 돌고 나면 queue 배열 안에 값이 없다는 것을 의미합니다. 이는 더 이상 감염된 컴퓨터와 연결된 컴퓨터가 없다는 의미입니다. 따라서 결과 값으로 방문한 visited의 요소 개수에 -1을 한 값을 반환합니다. 1번 컴퓨터부터 시작했기 때문에 1을 뺀 값이 정답이 됩니다.

 

 

---

글을 쓰다 보니 좀 더 자세하게 설명하고 싶은 마음에 글이 길어졌습니다ㅎㅎ 😮
저도 처음에 풀 때는 정말 이해가 안 가고 여러 다른 블로그를 방문해 가면서 제각각 다른 코드지만 문제를 푸는 방식에 대해서 계속 생각해 봤던 거 같습니다. 물론 저도 다른 유형의 문제를 풀게 된다면 처음부터 이 정도로 해설이 안될 거 같습니다ㅋㅋ;;

그래도 혹시나 이 문제에 대해서 제가 생각하는 부분이 필요한 분이 계실 수도 있으니 가볍게 읽어주시고 다른 문제들도 파이팅 하십시오ᄒᄒ👏