[BAEKJOON] 2606_바이러스

오랜만에 다시 알고리즘 문제를 풀기 시작!

백준의 1260번 DFS와 BFS, 7576번 토마토에 이어 3번째 문제이다.

전부 예전에 풀었던 문제들이나 오랜만에 시작하는거니까 다시 풀어보았다!!!

나름 열심히 공부 했었는데...9개월 만에 시작하려니 가물가물하다.

그러나!! 최근 어쩔수없는 상황속에서 다른 사람의 코드를 이해하던 말던 오랜시간 쳐다보고 있으니...

코딩에 관한 실력은 약간 늘은 것 같은 기분...??이다.

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

풀이

예전에는 DFS로만 풀었으나, 이번에는 BFS로도 풀어보았다.

방법은 여러개가 있겠으나, 나는 DFS와 BFS로 문제를 풀기 위해 '인접배열'을 사용하였다. 두 컴퓨터가 서로 연결되어 있다는 것을 표시하기 위해서이다. 인접배열은 이렇게 한 쌍?연결선?으로 이어지는 그래프 문제에서 자주쓰이는 것 같다. 인접배열은 별도의 설명은 하지 않겠다.

1. DFS

시작점인 1을 기준으로 재귀 함수를 사용하여 연결되어 있는 Computer들을 따라 들어가는 방법이다. 방문한 지점을 다시 방문하는 것을 방지하기 위하여 배열을 사용하여 체크해주었다. 방문 지점을 체크할 때 바이러스에 감염된 컴퓨터의 개수를 +1 해준다.

위의 문제 예시에서는 1-2-3-5-6순으로 방문한다.

2. BFS

1과 연결된 컴퓨터들을 큐에 넣어 준 후, 순서대로 pop 해주어 1과 인접한 computer들부터 방문하는 방법이다. DFS와 마찬가지고 방문하였던 지점을 다시 방문하는 것을 방지하기 위해 배열을 사용하여 방문 지점을 체크해준다. 이때 마찬가지로 감염된 컴퓨터의 개수를 +1해준다.

위의 문제 예시에서는 1->3->5->2->6 순으로 방문한다.

이 경우 while문에 들어가여 pop 해준기전에 1을 방문하였다고 체크해주거나 아니면 감염된 컴퓨터의 개수에서 -1을 해주어야 한다. 나는 -1 해주었다.

제출한 코드

DFS

BFS