바이러스
| 1 초 | 128 MB | 212934 | 101687 | 67006 | 46.275% |
문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
예제 입력 1 복사
7
6
1 2
2 3
1 5
5 2
5 6
4 7
예제 출력 1 복사
4
DFS BFS 문제 중에 그나마 쉬운... 바이러스를 풀기로 했다.
그런데... 뭐 어떻게 풀어야 해
문제 쳐다보고 있는데 문제 출처가???
예?????????? 초등부요??????????????
정말..
맴이 힘들다..........
입력 받는 건 한 줄 컴퓨터의 수 받고
그 담 한 줄 연결된 컴퓨터 쌍의 수
글고 그 담에 연결 컴퓨터 번호 쌍이 들어오네
출력은 1번 컴퓨터가 웜 바이러스 걸렸을 때 웜 바이러스에 걸리게 되는 컴퓨터의 수
타고타고타고 들어가면 다 바이러스에 걸린다 이 말이네
그냥 컴퓨터 다 갖다 버리면 아 ㄴ돼?? 왜 컴퓨터의 수를 구하는 거야.
입력부터 문제 발생.. 저 컴퓨터들을 어떤 타입으로 입력받아야 할까
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int computerCount = Integer.parseInt(br.readLine());
int connectCount = Integer.parseInt(br.readLine());
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= computerCount; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < connectCount; i++) {
Stirng[] input = br.readLine.split(" ");
int a = Integer.parseInt(input[0]);
int b = Integer.parseInt(input[1]);
graph.get(a).add(b);
graph.get(b).add(a);
}
boolean visited[] = new boolean[computerCount + 1];
int virusComputersCount = dfs(1, graph, visited) - 1;
System.out.println(virusComputersCount);
}
public static int dfs(int node, List<List<Integer>> graph, boolean[] visited) {
visited[node] = true;
int count = 1;
for (int connected : graph.get(node)) {
if (!visited[connected]) {
count += dfs(connected, graph, visited);
}
}
return count;
}
}
열심히 짰는데...
컴파일 오류 났다;;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int computerCount = Integer.parseInt(br.readLine());
int connectCount = Integer.parseInt(br.readLine());
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= computerCount; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < connectCount; i++) {
String[] input = br.readLine().split(" ");
int a = Integer.parseInt(input[0]);
int b = Integer.parseInt(input[1]);
graph.get(a).add(b);
graph.get(b).add(a);
}
boolean visited[] = new boolean[computerCount + 1];
int virusComputersCount = dfs(1, graph, visited) - 1;
System.out.println(virusComputersCount);
}
public static int dfs(int node, List<List<Integer>> graph, boolean[] visited) {
visited[node] = true;
int count = 1;
for (int connected : graph.get(node)) {
if (!visited[connected]) {
count += dfs(connected, graph, visited);
}
}
return count;
}
}
오타랑.. 빠진 import문 추가 괄호도 추가ㅎ.. 역시 IDE 있없은 큰 차이다...
통과~
DFS BFS는 뭔가 알 것 같은데 막상 쌩으로 코드 짜려면 잘 모르겠다..
일단 코드에 주석 좀 달아보겠음
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int computerCount = Integer.parseInt(br.readLine()); // 컴퓨터 수
int connectCount = Integer.parseInt(br.readLine()); // 연결 쌍 수
List<List<Integer>> graph = new ArrayList<>(); // 이중 리스트를 사용한 그래프 초기화 (컴퓨터 번호는 1번부터 시작하므로 0번은 더미로 추가)
for (int i = 0; i <= computerCount; i++) {
graph.add(new ArrayList<>());
}
// 연결 정보 입력받아서 양방향 그래프 구성
for (int i = 0; i < connectCount; i++) {
String[] input = br.readLine().split(" ");
int a = Integer.parseInt(input[0]);
int b = Integer.parseInt(input[1]);
graph.get(a).add(b);
graph.get(b).add(a);
}
boolean visited[] = new boolean[computerCount + 1]; // 방문 여부 배열 초기화(1부터 쓸 거기 때문에 사이즈 때문에 1 더함)
int virusComputersCount = dfs(1, graph, visited) - 1; // 1번 노드부터 시작하니까 1 넣고 시작. 1번 노드 제외해야 하니까 1 빼줌
System.out.println(virusComputersCount); // 출력
}
public static int dfs(int node, List<List<Integer>> graph, boolean[] visited) {
visited[node] = true; // 방문했으니까 true로 바꿈
int count = 1; // 현재 노드 감염 수. 자기 자신 1에서 시작하니까
// 연결된 컴퓨터 중 아직 방문 안 한 컴퓨터만 방문
for (int connected : graph.get(node)) {
if (!visited[connected]) {
count += dfs(connected, graph, visited);
} // 연결된 컴퓨터 재귀로 방문해서 count에 더해주기
}
return count; // 총 감염 수 return
}
}
📌 인접 리스트란?
각 정점(컴퓨터)이 어떤 정점들과 연결되어 있는지를 리스트로 표현한 것.
예를 들어, 컴퓨터가 4대 있고 다음과 같이 연결되어 있다고 해보죠:
- 1 - 2
- 2 - 3
- 1 - 4
이 문제는 인접 리스트였다... 코드 달다가 찾아봤다. 이런 문제는 뭐라고 하는지.
글고 도저히 입력을 어떻게 받아야 할 지 모르겠어서 찾아보다가 2차원 리스트로 입력을 받으면 된다는 걸 찾았다.
✅ 2차원 리스트란?
간단히 말하면,
리스트 안에 또 다른 리스트들이 들어 있는 자료구조이다.
List<List<Integer>> list2D = new ArrayList<>();
// 0행
list2D.add(new ArrayList<>());
list2D.get(0).add(1);
list2D.get(0).add(2);
// 1행
list2D.add(new ArrayList<>());
list2D.get(1).add(3);
list2D.get(1).add(4);
이렇게 코드를 짰다고 했을 때,
[
[1, 2], // 0번째 행
[3, 4] // 1번째 행
]
이런 구조가 되는 거다!! 2차원 배열 생각하면 더 쉬울 수도..??
int a = list2D.get(0).get(1); // 0번째 행의 1번째 값 → 2
int b = list2D.get(1).get(0); // 1번째 행의 0번째 값 → 3
값은 요렇게 가져온다.
for (int i = 0; i < list2D.size(); i++) {
for (int j = 0; j < list2D.get(i).size(); j++) {
System.out.print(list2D.get(i).get(j) + " ");
}
System.out.println();
}
순회할 때는 이렇게!
배열은 사이즈가 고정되는 반면, 리스트는 동적이라서 추가, 변경에 용이하다.
그렇다면 메모리는? 배열이 더 적게 쓴다고 한다.
| 항목 | 배열 | 리스트 |
| 크기 조절 | ❌ 불가능 | ✅ 가능 |
| 인덱스로 접근 | ✅ 빠름 | ✅ 빠름 |
| 유연성 | ❌ 낮음 | ✅ 높음 |
| 선언 문법 | 단순 | 약간 복잡 |
| 2차원 구조 | int[][] | List<List<Integer>> |
✅ 언제 배열, 언제 리스트?
| 크기가 고정됨 | ➡️ 배열 (int[], int[][]) |
| 크기 변경 가능해야 함 | ➡️ 리스트 (ArrayList) |
| 속도 최우선 | ➡️ 배열 |
| 연결 정보/그래프 구조/유연성 필요 | ➡️ 리스트 |
상황에 맞게 잘 사용해보도록 하자.
웬만하면 리스트 쓸 듯...?? 그렇게 속도 제한이 빡빡하지 않으면...
'백준 풀기' 카테고리의 다른 글
| 백준 1991번: 트리 순회 with Java (0) | 2025.05.18 |
|---|---|
| 백준 2178번: 미로 탐색 with Java (0) | 2025.05.11 |
| 백준 1431번: 시리얼 번호 with Java (0) | 2025.04.24 |
| 백준 18870번: 좌표 압축 with Java (1) | 2025.04.22 |
| 백준 17478번: 재귀함수가 뭔가요? with Java (0) | 2025.04.21 |