/* 이것은 dfs 인지 bfs 인지 파악해보도록 하겠습니다. 신종 바이러스 웜 바이러스 네트워크 한 컴퓨터 웜 바이러스, 컴퓨터와 네트워크 상에 연결되어 있는 모든 컴퓨터는 웜 바이러스 바이러스에 걸리게 되는 컴퓨터의 수를 출력 이거 2차원 행렬만들어서, 행렬로 만들어서 풀이가 가능할까? 이렇게 만들고 1행에 대해서 포문을 돌려서 연결되어 있는 것을 보면 2 , 5입니다. 이것을 큐에 넣습니다. 그리고 큐를 하나씩 꺼냅니다. 그럼 2입니다. 여기서 2와 연겨되어 있는것 1, 3, 5 입니다. 그런데 여기서 1 5 에 대해서는 처리했으므로, 처리했다고 하는 visit[] 배열이 필요하겠습니다. 오께이. 그럼 2 5 3 이 들어가고 2 처리됬으니, 5 처리 하려면 1 2 6 인데 1 2는 처리한적이 있으니 6 이들어옵니다. 3 처리합니다 2 처리 됬으니 이제 큐가비었으니 끝입니다. 오께이. 1 2 3 4 5 6 7 1 o o 2 o o o 3 o 4 o 5 o o o 6 o 7 o */ #include <iostream> #include <queue> using namespace std; int map[100][100]; int check[100]; int n, k, a, b, cnt; void problemIn() { cin >> n; cin >> k; for (int i = 0; i < k; i++) { cin >> a >> b; map[a-1][b-1] = 1; map[b-1][a-1] = 1; } } void solve() { int row; queue<int> que; que.push(0); check[0] = 1; while (!que.empty()) { row = que.front(); que.pop(); for (int i = 0; i < n; i++) { if (map[row][i] == 1 && check[i]==0) { que.push(i); check[i] = 1; } } } for (int i = 0; i < n; i++) { if (check[i] == 1) cnt++; } cout << cnt-1 << endl; } int main() { problemIn(); solve(); return 0; } |
행렬을 만들고, 그에 대해서 연결되는 것들을 bfs 처리하였습니다. 오께이요. 오께이요. bfs 와 dfs 에 대해서 명확히 알것. 계속해서 답보고 풀다가 이것 처음으로 내 힘으로 푸니, 자신감이 업됬습니다. 오께이. 그럼 bfs 와 큐의 사용법은 어느정도 익혔다고 볼 수 있습니다. 점점 더 복잡한 dfs 와 bfs 를 풀어보도록 하겠습니다. |