Backjoon Online Judge 

"2606번 : 바이러스" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/2606



문제 및 코드 설명입니다.


'2606번 : 미로탐색' 문제의 경우 BFS나 DFS를 적용하면 매우 쉽게 풀 수 있는 문제였습니다.

문제 설명은 BFS에 더 가깝지만 DFS로 풀어도 상관없는 문제라 DFS를 적용하여 풀어 보았습니다.


먼저 컴퓨터의 연결 상태를 저장할 2차원 배열과 방문 유뮤를 저장할 visit 배열을 만들었습니다.

2차원 배열에는 연결 정보를 저장하고 1번을 시작점으로 DFS를 적용해서 문제를 해결하였습니다.

(DFS 알고리즘을 알고 있다면 아래 DFS함수는 바로 이해가 될 것이라 생각합니다.)



코드는 C++로 작성하였습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
 
#define Max 101
 
using namespace std;
 
int num;    //컴퓨터의 수
int result;    //결과 값 저장
int computer[Max][Max] = { 0, };
int visit[Max] = { 0, };
 
void dfs(int start) {
    visit[start] = 1;
    for (int i = 1; i <= num; i++) {
        if (!visit[i] && computer[start][i]) {
            result++;
            dfs(i);
        }
    }
}
 
int main() {
    int c_pair, temp1, temp2;
    cin >> num >> c_pair;
    while (c_pair--) {
        cin >> temp1 >> temp2;
        computer[temp1][temp2] = computer[temp2][temp1] = 1;
    }
    dfs(1);
    cout << result << endl;
}


저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

10216번 : Count Circle Groups (DFS)  (0) 2018.05.31
2667번 : 단지번호붙이기  (0) 2018.05.29
2178번 : 미로탐색  (0) 2018.05.17
7569번 : 토마토  (0) 2018.05.17
7576번 : 토마토  (0) 2018.05.16

티스토리툴바