[백준2606] 바이러스 - 완전탐색, dfs

문제

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

2606번: 바이러스

 

문제 분석

시간 복잡도

• 컴퓨터수 (노드 수): 100대
• 엣지수:
  모름
  최악의 경우 완전그래프 형태: N(N-1) / 2 
• 이미 방문한 노드는 재방문 필요 X
• 방문한 노드에서 연결된 노드 재귀적 방문
• O(100)
  연결리스트 배열: O ( V + E ) → O ( 100 + 100^2 )
  2차원 배열: O ( V^2 ) → O ( 100^2 )

문제 유형

• 시간복잡도상 완전탐색 가능
• 완전탐색 (dfs)

 

 

설계

dfs 설계

dfs는 기본적으로 "탐색" 알고리즘이다. 즉,

1. 연결된 곳 (순회할 수 있는 곳)이 어디인지
2. 연결된 곳으로 갈 수 있는지

파악하는 것이 가장 중요하다고 할 수 있다. 전체적인 설계는 아래와 같다.

 

 

1. 체크인: 방문체크 
2. 목적지: 없음
3. 연결된 곳: 연결리스트 배열로 표현
4. 갈 수 있는가?: 방문 안한 노드
5. 체크아웃: 없음 (로직상, 방문체크 해제 필요 x)

 

별도의 목적지(base case)는 없다. 방문체크 해제 없이 방문 안한 곳만 방문하는 재귀 메소드이기 때문에 로직상, 스택 오버플로우의 걱정도 없다.

 

연결된 곳을 주목하자. 연결된 곳을 파악하려면, 그래프를 적절한 형태로 표현해야 한다. 그래프를 표현하는 방식 중, 2차원 배열로 표현하는 방법과 연결리스트 배열로 표현하는 방법이 있다. 두 가지 모두 장.단점이 있고 상황에 따라 선택하여 구현하면 된다.

 

체크인, 체크아웃을 주목하자. 해당 문제는 한 번 방문한 노드는 더 이상 방문할 필요가 없다. 따라서, 방문 시에 방문체크를 해주고, 재귀 메소드 탈출 시 별도의 방문체크는 해제할 필요 없다. 체크인, 체크아웃은 문제의 로직마다 달라지며 문제의 요구사항을 정확히 파악하여 정확히 설계하는 것이 중요하다.

 

수도 코드

dfs (int node) {
...
// 연결된 곳
for (int x: board[방문한 노드])
	// 갈 수 있는가?
    if(!visited[x])
    	// 간다
        dfs (x)
...
}

 

 

구현

코드

public class BOJ2606_바이러스 {
	static final int nodeCount = 101;
	static int computerCount, edgeCount;
	static int visitCount = -1;
	static List<Integer>[] adj = new ArrayList[nodeCount];
	static boolean[] visited = new boolean[nodeCount];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		computerCount = Integer.parseInt(br.readLine());
		edgeCount = Integer.parseInt(br.readLine());

		for (int i = 1; i < nodeCount; i++) {
			adj[i] = new ArrayList<>();
		}

		while (edgeCount-- > 0) {
			st = new StringTokenizer(br.readLine());
			while (st.hasMoreTokens()) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());

				adj[from].add(to);
				adj[to].add(from);
			}
		}
		dfs(1);
		System.out.println(visitCount);
	}

	private static void dfs(int node) {

		// base case
		// 체크인
		visited[node] = true;
		visitCount++;
		// 목적지인가? (없음)

		// recursive case
		// 연결된 곳 순회
		for (int nextNode : adj[node]) {
			// 갈 수 있는가?
			if (!visited[nextNode]) {
				dfs(nextNode);
			}
		}
	}
}

 

 

결과

 

 

기록

• 날짜: 2022-12-21
• 소요시간: 25분

 

보완 사항

• 2차원배열, 연결리스트배열을 중복없이 완전탐색할 경우 시간복잡도 차이