[TIL 2024. 03. 12] : 바이러스_dfs

오늘 한 일

• 오늘의 코드카타 8문제
• 오후 알고리즘 세션
• 알고리즘 문제 복습: 바이러스, 프린트 큐 위주
• TIL 작성

 

바이러스(BOJ)

이 문제에서 배울 수 있는 중요 개념들은 다음과 같다

• 인접리스트 (cf. 인접행렬) => 특히, 쌍방향
• visited 사용
• dfs(깊이 우선 탐색 w.graph) + 재귀

대략적인 순서는..

1. 입력을 받음 (N은 노드(컴퓨터)의 수, M은 연결 순써상의 수)

2. 노드 간 연결을 저장할 변수, visit여부를 저장할 변수(visited) 선언해야 함

 

단, 이때 변수를 선언할 때는 두 변수 다 인접리스트로 해야한다.

특히, 전자는 []로 초기화된 1차원의 인접리스트를 선언하고, 후자는 0으로 초기화된 1차원의 인접리스트를 선언해야 한다는 점이 중요하다.

 

또, 이 인접리스트들은 모두 for문을 사용하는데, 나는 이때 range할 범위를 헷갈림. 개인적으로는 1부터 시작하는 게  덜 헷갈려서 '1,N+1'을 range로 하면 오류남. 왜냐하면 이 때의 요소는 총 1~N이니, 총 N개이다.

 

그런데, 뒤에 나오는 변수 a,b는 각각 graph의 인덱스가 됨. 내가 아무리 앞에서 1을 인덱스 시작으로 하려고 해도, 뒤에 a,b의 '요소값'이 1부터 시작하는데, 이게 graph의 인덱스가 되어야 하므로(=디폴트가 0) 나중에 graph[7]에 접근할 수 있으려면 range는 'N+1'로 해야함.

#입력예제1
7
6
1 2
2 3
1 5
5 2
5 6
4 7

 

3. M을 range로 하는 for문에서 input(=노드 연결현황)을 각각 변수(a,b)로 받음. dfs함수를 선언한다

이때, dfs함수는 parameter로 1부터 시작하는 cur(=current node)를 받도록 한다. 이렇게 하는 이유는 이 'cur(=현재 노드)'을 graph와 visited의 인덱스로 활용해야 하기 때문이다. 

여기서 for문을 돌기 전에 visited에 방문처리를 하면 깔끔하다. 즉, dfs함수 호출과 동시에 방문처리를 하는게 좋음. 이렇게 하면 모든 연결된 노드에 대해 방문처리를 한 다음에, 해당 노드들을 방문하게 됨. (for문 안에 방문처리를 넣으면?)

 

4. dfs함수를 호출하고, visited를 sum해서 print한다

visited는 0,1로 이루어진 변수이므로 count를 세기 위해 바로 sum해도 무방하다

이때에 주의할 것은 sum에서 노드1을 방문한 것으로 표시된 것은 빼줘야 한다. 그래야 노드1이 감염된 영향으로 바이러스에 감염된 노드들의 수를 셀 수 있기 때문이다

 

코드들이 어떻게 돌고 있는지 확인하기 위해, 디버깅 모드도 사용하고 중간중간 print문을 찍어봤다

 

graph 맨 앞의 빈 리스트는 인덱스0을 의미하므로, 무시하면 된다

나중에 문제에서 요구하는 1번 컴퓨터로 인해 감염된 컴퓨터의 수를 출력하기 위해 visited를 sum할 것이기 때문이다. (0번 노드는 어차피 아무 것도 없으므로 sum에 영향을 주지 않는다. 마찬가지로 0더해도 아무런 영향이 없다)

 

dfs함수가 호출되면 1번 인덱스의 모든 요소에 방문처리가 일단 되고, 그 다음에 각각의 노드들을 방문한다.

예를 들면, 1번 노드에 방문 처리 이후에 for문을 돌면서 2, 5 방문하게 된다. 하지만 이 코드는 깊이 우선탐색 이므로, 2를 방문하다가 재귀적으로 2번째 노드의 3, 5 등을 방문하게 된다. 따라서 재귀를 타다 보면 1번 노드의 5를 방문 하기 전에 2를 방문하면서 이미 5를 방문하게 된다.

 

이런 식으로 방문한 노드에 연결된 다른 노드들까지 재귀를 타고 가다보면, 더이상 갈 수 있는 연결된 노드가 없는 지점에 이르게 되고, for문 그리고 visited를 sum해서 결과값이 출력된다.