백준 알고리즘 2606 (바이러스) - C++, Python

[문제] 백준 알고리즘 2606 (바이러스)

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

2606번: 바이러스

 

노드와 간선이 주어졌을 때, 완전탐색을 하라는 문제.

나는 개인적으로 DFS를 좋아해서 DFS로 진행헀다.

 

단순하게 갯수 카운팅만 하기보다는, 루트를 출력할 수 있게 짜고

그 루트의 길이 -1(시작하는 1 제외)를 출력해주었다.

Stack과 재귀함수를 이용했고, C++에서는 나중에 BFS에서도 쓸 수 있도록

Deque(Stack과 Queue의 효율적 구조)에 익숙해지려고 이용해봤다.

 

[C++]

#include <iostream>
#include <deque>
using namespace std;

int N = 0, M = 0;
int graph[101][101] = { 0, };
bool visited[101] = { 0, };
deque<int> stk;

void solve_dfs(int v) {
	stk.push_back(v);
	visited[v] = 1;
	for (int i = 1; i <= N; i++) {
		if (!visited[i] && graph[v][i]) {
			solve_dfs(i);
		}
	}
}

int main() {
	cin >> N;
	cin >> M;
	   
	int x = 0, y = 0;
	for (int i = 0; i < M; i++) {
		cin >> x >> y;
		graph[x][y] = graph[y][x] = 1;
	}
	solve_dfs(1);
	cout << stk.size()-1;
}

 

[Python]

import sys
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    link = tuple(map(int, input().split()))
    graph[link[0]].append(link[1])
    graph[link[1]].append(link[0])

visited = [False] * (N+1)
stack = []
def solve_dfs(v):
    stack.append(v)
    visited[v] = True
    for next_v in graph[v]:
        if not visited[next_v]:
            solve_dfs(next_v)
    return
solve_dfs(1)
print(len(stack)-1)