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
- 플러터
- 성능테스트
- backend
- 후기
- 로드밸런서
- 멘토링
- FLAB
- 백엔드
- Spring
- error
- grafana
- 알고리즘
- F-Lab
- nGrinder
- EC2
- Flutter
- 도커
- 부트캠프
- github
- 자바백엔드
- 코딩테스트
- 자바
- 에프랩
- MySQL
- 데이터구조
- AWS
- 트러블슈팅
- redis
- 레디스
- java
Archives
- Today
- Total
민스씨의 일취일장
Java | 백준 11724 연결 요소의 개수 본문
반응형
백준 11724 연결 요소의 개수 문제에 대한 글입니다.
백준 11724 연결 요소의 개수
문제
문제는 아래 링크에서 확인할 수 있다.
풀이
재귀 호출을 이용한 DFS
2차원 배열을 이용해서 연결 정보를 입력받느다. 그 다음 재귀 호출을 이용해 DFS를 수행한다.
특징
정보는 2차원 배열에 담았지만, 방문 이력은 1차원 배열에 담는다. 연결 정보 상관없이, 연결 돼 있는 노드에 일단 방문했는지 여부만 체크하면 되기 때문에, 방문 이력은 1차원으로 충분하다.
전체코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class baekjoon11724 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int node, edge;
static boolean[][] map;
static boolean[] visited;
static void input() throws IOException{
st = new StringTokenizer(br.readLine());
node = Integer.parseInt(st.nextToken());
edge = Integer.parseInt(st.nextToken());
map = new boolean[node+1][node+1];
visited = new boolean[node+1];
for(int i=0; i<edge; i++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
map[a][b] = true;
map[b][a] = true;
}
}
static int execute(){
int result = 0;
for(int i=1; i<node+1; i++){
if(!visited[i]){
dfs(i);
result++;
}
}
return result;
}
static void dfs(int x){
if(!visited[x]) {
visited[x] = true;
for(int i=1; i<node+1; i++){
if(map[x][i]){
dfs(i);
}
}
}
}
public static void main(String[] args) throws IOException {
input();
System.out.println(execute());
}
}
배운 점
연결 정보를 2차원 배열에 담고, 방문 이력은 1차원 배열로 체크하는 방법을 알게 되었다. 차원을 줄이는 개념이기 때문에 다른 부분에서도 이용할 수 있을 것이라고 생각이 든다.
728x90
반응형
'Data Structure & Algorithm > Java' 카테고리의 다른 글
Java | 백준 2667 단지번호 붙이기 (0) | 2024.02.09 |
---|---|
Java | 백준 11057 오르막 수 (0) | 2024.02.09 |
Java | 백준 26169 세 번 이내에 사과를 먹자 문제풀이 및 분석 (0) | 2024.02.08 |
Java | 백준 1388 바닥 장식 문제풀이 및 분석 (0) | 2024.02.07 |
Java | 백준 13300 방배정 풀이 전략 기록 (0) | 2023.08.09 |