[백준 | 파이썬3] 2606. 바이러스- dfs

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

2606번: 바이러스

> dfs 활용

단방향 그래프가 아닌 양방향 그래프임에 주의해야한다. 

 

▷ 처음에는 단방향 그래프로 다음과 같이 구현했다. 

그러나 위 코드는 다음과 같은 예제는 풀지 못한다. 

위와 같은 그래프가 있다고 할때 단방향 그래프는 1번 노드에서 출발했을 때 3번과 2번노드와 연결되어 있다고 인식하기 때문에 다음과 같이 1과 연결된 노드의 수로 2를 출력한다. 

 

 

▷ 그러나 문제에 따르면 1번 노드는 2,3번 노드 뿐만 아니라 4번 노드와도 연결되어있기 때문에 3을 출력해야한다. 이를 위해선 연결되어 있는 노드는 두 방향에서 연결되어 있음을 나타내는 양방향 그래프를 사용해야하기 때문에 양방향 그래프를 나타내는 코드로 다시 구현했다. 

 

단방향과 달리 행렬로 그래프를 표현했고 두 노드가 연결되어 있으면 두 노드의 행렬위치 모두에 다음과 같이 1을 넣어주었다.

단방향 그래프에서 사용했던 예시를 양방향 그래프 코드로 다시 구현해보면 의도했던 결과가 나옴을 볼 수 있다.