[BOJ]2606ウイルス
11424 ワード
質問する
新型ウイルスワームウイルスはネットワークを通じて伝播する.1台のコンピュータがワームウイルスに感染した場合、ネットワークに接続されているすべてのコンピュータがワームウイルスに感染します.
例えば、<図1>に示すように、7台のコンピュータがネットワークに接続されているとする.1番のコンピューターがワームウイルスに感染した場合、ワームウイルスは2番と5番のコンピューターを経て3番と6番のコンピューターに伝播し、2、3、5、6の4台のコンピューターがワームウイルスに感染する.しかし、4番と7番は1番とネットワーク接続がないため、影響を受けません.
ある日、1番のパソコンがワームウイルスに感染した.コンピュータの数とネットワーク上の情報が相互に接続されている場合は、コンピュータを介してワームウイルスに感染したコンピュータの数を出力するプログラムを作成します.
入力
最初の行はコンピュータの数を示します.パソコンの数は100以下で、1台あたり1番から順番に番号をつけます.2行目は、ネットワークに直接接続されているコンピュータペアの数を示します.次に、ネットワークに直接接続された各行の1対のコンピュータの番号ペアが与えられる.
しゅつりょく
1番コンピュータがワームウイルスに感染した場合、1番コンピュータを介してワームウイルスに感染したコンピュータの数を1行目に出力する.
入力例1
7
6
1 2
2 3
1 5
5 2
5 6
4 7
サンプル出力1
4
に答える
1番パソコンに接続しているパソコンの数を探している問題です.
図に何の値が含まれているのか分からないため,バイナリルックアップツリーのようにソートされず,またルックアップパスの問題であるため,
Recursive DFS
を用いた.1番パソコンに接続されているパソコンだけが貴重な数で動く.
コード#コード#
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
* 1. input:
* 1) 컴퓨터의 수. 이는 1 이상 100 이하. 1번부터 차례로 컴퓨터의 번호 매겨짐
* 2) 연결된 컴퓨터 쌍의 수(간선 수)
* 3) 간선 수만큼 연결된 컴퓨터의 번호 쌍
* 2. output: 1번 컴퓨터를 통해 바이러스에 걸린 컴퓨터의 수
* 3. constraints:
* 4. edge case:
* 5. brute force: dfs recursive
* 6. code
* */
public class Main {
static int n, pairs, start, end, count = 0;
static int[][] map;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
pairs = Integer.parseInt(br.readLine());
map = new int[n + 1][n + 1];
visited = new boolean[n + 1];
for (int i = 0; i < pairs; i++) {
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());
map[start][end] = map[end][start] = 1;
}
dfs(1);
System.out.println(count);
}
static void dfs(int startPoint) {
visited[startPoint] = true;
for (int i = 1; i <= n; i++) {
if (map[startPoint][i] == 1 && visited[i] == false) {
count++;
dfs(i);
}
}
}
}
Reference
この問題について([BOJ]2606ウイルス), 我々は、より多くの情報をここで見つけました https://velog.io/@ffwang/BOJ-2606-바이러스テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol