백준 2606번
https://www.acmicpc.net/problem/2606
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
7
6
1 2
2 3
1 5
5 2
5 6
4 7
4
DFS/BFS공부하려고 문제를 찾아서 풀려고 했는데,
풀이 방법을 생각하다보니 Floyd-Warshall 알고리즘으로도 충분히 풀 수 있겠다는 생각을 했다.
Floyd-Warshall은 원래 최소비용을 구하는 알고리즘이지만,
출발점으로부터 모든 경로를 탐색할 수 있다는 장점이 있기 때문에 1에서만 출발하는 조건에서 적한합 알고리즘이라고 판단했다.
그래서 먼저 Floyd-Warshall을 통해서 풀고
DFS, BFS를 이용해서 총 3가지 방법을 이용해서 풀어보기로 했다.
arr[][]
의 2차원 배열을 먼저 생성한다.
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
arr[y][x] = 1;
arr[x][y] = 1;
}
여기서 Floyd-Warshall 알고리즘을 이용하기 위해
arr[i][j]
와 arr[j][i]
둘 다 1로 바꿔준다.
arr[][]
가 완성되면,
Floyd-Warshall알고리즘의 floyd() 함수를 실행한다.
floyd() 함수는
k
라는 다리를 통해 기존의 arr[i][j]
, arr[j][i]
로 이동할 수 있는 경로의 모든 곳에 1로 변환해준다.
즉, arr[i][k]
에서 arr[k][j]
둘 다 1일경우 이동할 수 있다고 판단하여 arr[i][j]
를 1로 변경해준다.
이렇게 되면 arr[1]
의 1로 된 값들이 1번 컴퓨터에서 이동할 수 있는 컴퓨터가 되므로
arr[1]
의 1인 값들을 result++
로 증가시켜
출력해주면 정답을 얻을 수 있게된다.
혹시 Floyd-Warshall알고리즘을 잘모르거나 한번 맛보고 싶으신 분들은
백준 11403 경로 찾기
위의 문제를 풀어보거나, 아래의 글을 읽어보길 바란다.
백준 11403 경로 찾기 풀이
문제를 풀고나서 아무래도 이 문제 자체가 DFS/BFS 문제다 보니 당연히 해당 알고리즘을 통해서도 풀어보는게 맞다는 생각을 해서
DFS, BFS를 이용해서 모두 풀어보았다.
DFS는 재귀를 사용했고, BFS는 Queue를 이용해서 탐색하는 반복은 똑같다
하지만 이 문제의 구조자체가 원래 양방향 그래프 개념을 가지고 있기때문에
(1,2)와 (2,1)은 같다는 것을 파악해야 한다.
그래서, 둘의 구조가 같기 때문에 arr[x][y] = arr[x][y] = 1
의 구조가 된다.
이 배열을 완성하기 위해 arr
은 2차원 배열로 만들어 주지만, 방문 여부를 표시하는 visit[]
은 우리는 출발점인 1번 컴퓨터만 따지면 되기때문에 visit[]
은 1차원 배열로 만들어준다.
이후 방문을 했는지와 1인지를 파악해서 조건에 맞춰 result
를 증가시키면 정답을 얻을 수 있다.
풀어본 김에 또 비교를 안할 수 없지.
3가지 풀이를 비교해 보았다.
Floyd 알고리즘이 DFS/BFS보다는 아무래도 완전탐색 개념이다 보니 효율성이 좀 떨어질 수 밖에 없는 것 같다.
그래도 성공이라는 의미가 있는거니까 수확은 있다.
DFS/BFS 알고리즘 문제로 알고 들어왔지만, 다름 알고리즘을 응용해서 풀었다.
칭찬해 나 자신
import java.util.*; import java.io.*; public class Main { static int arr[][]; static int N, M; static int result = 0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; N = Integer.parseInt(br.readLine()); // 컴퓨터의 수 M = Integer.parseInt(br.readLine()); // 컴퓨터 쌍의 수 arr = new int[N+1][N+1]; for(int i=0; i<M; i++) { st = new StringTokenizer(br.readLine()); int y = Integer.parseInt(st.nextToken()); int x = Integer.parseInt(st.nextToken()); arr[y][x] = 1; arr[x][y] = 1; } floyd(); // 0과 자신인 1은 제외, 2부터 시작 for(int i=2; i<N+1; i++) { if(arr[1][i] == 1) { result++; } } System.out.println(result); } // End of main static void floyd() { for(int k=0; k<N+1; k++) { for(int i=0; i<N+1; i++) { for(int j=0; j<N+1; j++) { if(arr[i][k] == 1 && arr[k][j] == 1) { arr[i][j] = 1; } } } } } // End of floyd } // End of class
import java.util.*; import java.io.*; public class Main { static Queue<Integer> que = new LinkedList<>(); static int arr[][]; static boolean visit[]; static int N, M; static int result = 0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; N = Integer.parseInt(br.readLine()); // 컴퓨터의 수 M = Integer.parseInt(br.readLine()); // 컴퓨터 쌍의 수 visit = new boolean[N+1]; arr = new int[N+1][N+1]; for(int i=0; i<M; i++) { st = new StringTokenizer(br.readLine()); int y = Integer.parseInt(st.nextToken()); int x = Integer.parseInt(st.nextToken()); arr[y][x] = 1; arr[x][y] = 1; } BFS(); System.out.println(result); }// End of main public static void BFS() { que.offer(1); visit[1] = true; while( !que.isEmpty() ) { int node = que.poll(); for(int i=1; i<N+1; i++) { // 1이 아니거나 visit[]이 true일 경우, 그냥 통과 if(arr[node][i] != 1 || visit[i] == true) { continue; } que.offer(i); visit[i] = true; result++; } } } // End of BFS } // End of class
import java.util.*; import java.io.*; public class Main { static int arr[][]; static boolean visit[]; static int N, M; static int result = 0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; N = Integer.parseInt(br.readLine()); // 컴퓨터의 수 M = Integer.parseInt(br.readLine()); // 컴퓨터 쌍의 수 visit = new boolean[N+1]; arr = new int[N+1][N+1]; for(int i=0; i<M; i++) { st = new StringTokenizer(br.readLine()); int y = Integer.parseInt(st.nextToken()); int x = Integer.parseInt(st.nextToken()); arr[y][x] = 1; arr[x][y] = 1; } DFS(1); System.out.println(result); } // End of main static void DFS(int node) { visit[node] = true; for(int i=1; i<N+1; i++) { if(arr[node][i] == 1 && visit[i] == false) { DFS(i); result++; } } } // End of DFS } // End of class