티스토리 뷰

단순하게 BFS 그대로 적용하면 되는 문제였습니다.

그런데 조금 다른 생각이 들었던 부분은 바이러스가 걸린 컴퓨터는 곧 방문을 했다는 것이기 때문에

별도로 Counter 변수를 사용하지 않고 Visited가 TRUE인 정점의 갯수를 사용해보았습니다.

그런데 결과적으로 별도의 Counter를 선언하고, 방문 표시와 함께 Counter를 1씩 증가시키는 것이 더욱 빨랐습니다.


Visited 배열 사용한 방법

Visited의 값이 TRUE인 정점의 갯수를 세는 것은 JAVA8의 Stream API를 사용하였습니다.

자주 사용해서 익히기 위해서 요즘 생각이 날 때마다 적용해보고 있습니다.

Stream.filter.count를 이용하여 visited 배열에서 값이 true인 갯수를 세어 반환하도록 하였습니다.

재미는 있었지만 속도가 좋지 않더라구요.

package path.bj2606;

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
* Created by dasom on 2016-11-30.
*/
public class BreadthFirstSearch {

public static void main(String[] args) throws IOException {
//BufferedReader와 StringTokenizer 사용하여 읽어오는 방법. --> 이게 훨씬 빠르다.
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("Baekjoon\\input_data\\bj2606_input.txt")));
StringTokenizer st = null;

int nV = Integer.parseInt(br.readLine());
int nE = Integer.parseInt(br.readLine());

int[][] ad = new int[nV][nV];
Boolean[] visited = new Boolean[nV];
Arrays.fill(visited, Boolean.FALSE);

for (int i = 0; i < nE; i++) {

//배열인덱스는 0부터 시작이므로 -1을 한다.
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken()) - 1;
int v2 = Integer.parseInt(st.nextToken()) - 1;
ad[v1][v2] = ad[v2][v1] = 1;
}

Queue<Integer> queue = new LinkedList<>();

queue.offer(0);
visited[0] = true;

while (!queue.isEmpty()) {

// 현재 정점을 방문한다.
int cur = queue.poll();

for(int i=0; i<nV; i++){
if(ad[cur][i] == 1 && !visited[i]){
queue.offer(i);
visited[i] = true;
}
}

}

System.out.println(Arrays.stream(visited).filter(v -> v == true).count()-1);
}
}



Counter 변수 사용한 방법

이 방법은 처음에 생각했던 Counter 변수를 별도로 두어 카운팅하게 하는 방법이었습니다. 이게 훨~씬 빠르더라구요.

package path.bj2606;

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
* Created by dasom on 2016-11-30.
*/
public class BreadthFirstSearch {

public static void main(String[] args) throws IOException {
//BufferedReader와 StringTokenizer 사용하여 읽어오는 방법. --> 이게 훨씬 빠르다.
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("Baekjoon\\input_data\\bj2606_input.txt")));
StringTokenizer st = null;

int nV = Integer.parseInt(br.readLine());
int nE = Integer.parseInt(br.readLine());

int[][] ad = new int[nV][nV];
boolean[] visited = new boolean[nV];
int virusCounter = 0;

for (int i = 0; i < nE; i++) {

//배열인덱스는 0부터 시작이므로 -1을 한다.
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken()) - 1;
int v2 = Integer.parseInt(st.nextToken()) - 1;
ad[v1][v2] = ad[v2][v1] = 1;
}

Queue<Integer> queue = new LinkedList<>();

queue.offer(0);
visited[0] = true;

while (!queue.isEmpty()) {

// 현재 정점을 방문한다.
int cur = queue.poll();

for(int i=0; i<nV; i++){
if(ad[cur][i] == 1 && !visited[i]){
queue.offer(i);
visited[i] = true;
virusCounter++;
}
}

}

System.out.println(virusCounter);
}
}



속도/메모리 비교

아래가 첫번째 방법을 사용한 경우이고, 위에가 두번째 방법을 사용한 경우입니다. 속도 차이, 메모리 차이가 엄청납니다. 이건 두말할 것도 없이 Stream API를 쓰는게 무거운 것 같습니다.



댓글
댓글쓰기 폼
공지사항
Total
41,170
Today
70
Yesterday
59
링크
TAG
more
«   2018/07   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
글 보관함