문제

문제 링크 : https://www.acmicpc.net/problem/1260
수도코드 작성


작성한 코드
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer>[] graph;
static boolean[] visited;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 정점 개수
int M = Integer.parseInt(st.nextToken()); // 간선 개수
int V = Integer.parseInt(st.nextToken()); // 시작 정점
graph = new ArrayList[N+1];
for (int i=1; i<=N; i++){
graph[i] = new ArrayList<>();
}
// 간선 입력 (양방향)
for (int i=0; i<M; i++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph[a].add(b);
graph[b].add(a);
}
// 번호 작은거부터 방문하기 위해 정렬
for (int i=1; i<=N; i++){
Collections.sort(graph[i]); // ArrayList sort
}
// dfs
visited = new boolean[N+1];
dfs(V);
sb.append('\n');
// bfs
visited = new boolean[N+1];
bfs(V);
System.out.println(sb.toString());
}
static void dfs(int node){
visited[node] = true;
sb.append(node).append(' ');
for (int next : graph[node]){
if (!visited[next]){
dfs(next);
}
}
}
static void bfs(int start){
Queue<Integer> q = new LinkedList<>();
q.add(start);
visited[start] = true;
while (!q.isEmpty()){
int cur = q.poll();
sb.append(cur).append(' ');
for (int next : graph[cur]){
if(!visited[next]){
visited[next] = true;
q.add(next);
}
}
}
}
}
보완할 점 / 헷갈린 점
처음 DFS / BFS를 제대로 풀어봐서 이해하는데 시간이 조금 걸렸다
DFS는 재귀 형식으로 풀고
BFS는 큐에 넣고 다음 주소 부르라는 식으로 이해했는데 조금 더 문제들을 풀면서 이게 맞는 지 확인 해봐야겠다.
일단 처음에 ArrayList<Integer> 배열에 간선들을 다 넣고 시작하고
그리고 처음 정점들을 visited = true로 넣고 시작하는게 중요한 것 같다.
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 17478번 : 재귀함수가 뭔가요? - JAVA [자바] (1) | 2024.01.11 |
|---|---|
| [백준] 10845번 : 큐 - JAVA [자바] (0) | 2024.01.11 |
| [백준] 10816번 : 숫자 카드 2 - JAVA [자바] (0) | 2024.01.10 |
| [백준] 1920번 : 수 찾기 - JAVA [자바] (2) | 2024.01.09 |
| [백준] 10820번 : 문자열 분석 - JAVA [자바] (0) | 2023.01.15 |