Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 면접 필수 질문
- 프로그래머스 이중우선순위큐
- SQL
- DBASE&
- 이분탐색
- BFS
- 디베이스앤
- DP
- 백트래킹
- IT 면접 준비
- Spring Boot
- oracle ansi
- CJ DBASE&
- ansi sql 장점
- 위상정렬
- Gradle
- 그리디
- 백준
- JPA
- 이중우선순위큐 java
- DFS
- 디베이스앤 인턴 후기
- 개발자 면접 준비
- 프로그래머스 이중우선순위큐 java
- 프로그래머스
- Java
- ansi sql 단점
- oracle ansi sql
- 이중우선순위큐 자바
- 프로그래머스 이중우선순위큐 자바
Archives
- Today
- Total
쉬운 프로그래밍
[알고리즘] 백준 2606 바이러스 본문
public class BOJ_2606 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[][] map = new int[n + 1][n + 1];
boolean[] visited = new boolean[n + 1];
for (int i = 0; i < n + 1; i++) {
Arrays.fill(map[i], 0);
}
for (int i = 0; i < m; i++) {
String s = br.readLine();
StringTokenizer st = new StringTokenizer(s, " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
map[x][y] = 1;
map[y][x] = 1;
}
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(1);
visited[1] = true;
int count = 0;
while (!queue.isEmpty()) {
int k = queue.poll();
for (int i = 1; i < visited.length; i++) {
if (!visited[i] && map[k][i] == 1) {
queue.add(i);
visited[i] = true;
count++;
}
}
}
System.out.println(count);
}
}
맨 처음 바이러스가 감염된 컴퓨터로부터 인접 노드부터 차례대로 감염이 된다고 하였을 때, 감염된 컴퓨터의 대수를 카운트 하는 문제이다.
인접 노드부터 차례대로 감염이 된다고 하여서 BFS로 문제를 풀긴 하였는데,
단순 카운트 문제여서 DFS로 풀어도 문제는 없을것이다.
'알고리즘 > DFS, BFS' 카테고리의 다른 글
[알고리즘] 백준 7576 토마토 (0) | 2021.01.05 |
---|---|
[알고리즘] 백준 2178 미로탐색 (0) | 2021.01.05 |
[알고리즘] 백준 1012 유기농 배추 (0) | 2021.01.05 |
[알고리즘] 백준 2667 단지번호붙이기 (0) | 2021.01.05 |
[알고리즘] 백준 1260 DFS와 BFS (0) | 2020.11.02 |
Comments