B24479-깊이-우선-탐색-1
| 날짜 | 2024-04-08 |
| 사용 언어 | Java |
| 문제 유형 | #dfs#graphs#graph_traversal#sorting |
| 문제 URL | https://www.acmicpc.net/problem/24479 |
문제 #
문제 설명 #
제한사항 #
나의 풀이 (오답) #
예제 입력1 :
5 5 1
1 4
1 2
2 3
2 4
3 4
예제 출력1 :
1
2
3
4
0
1 -- 4
| / |
| / |
2 -- 3
반례 :
5 5 4
1 4
1 2
2 3
2 5
3 4
정답 :
2
3
4
1
5
1 -- 4
| |
| |
2 -- 3
|
|
5
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
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 start = Integer.parseInt(st.nextToken()); // 시작점
/** 무방향 그래프 **/
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
graph.add(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.get(a).add(b);
graph.get(b).add(a);
}
br.close();
/** dfs **/
// 노드를 저장 할 stack Stack<Integer> stack = new Stack<>();
stack.push(start);
// 방문 순서를 저장할 배열
int[] visitOrder = new int[N + 1];
// 방문 여부를 저장 할 배열
boolean[] visited = new boolean[N + 1];
// 시작 정점에 방문
visited[start] = true;
int order = 1;
while (!stack.isEmpty()) {
int vertex = stack.pop();
// 방문 할 때 마다 카운트 증가
visitOrder[vertex] = order++;
// 인접 정점은 오름차순으로 방문해야 하기 때문에 정렬
Collections.sort(graph.get(vertex));
// 꺼낸 정점과 연결 된 정점 탐색
for (int next : graph.get(vertex)) {
if (!visited[next]) {
stack.push(next);
visited[next] = true;
}
}
}
/** 출력 **/
StringBuilder sb = new StringBuilder();
// 1부터 시작이므로 기본 for 문 사용
for (int i = 1; i <= N; i++) {
sb.append(visitOrder[i]).append("\n");
}
System.out.println(sb);
}
}
나의 풀이 (정답) #
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
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 start = Integer.parseInt(st.nextToken()); // 시작점
/** 무방향 그래프 **/
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken()); // 간선의 한 정점
int v = Integer.parseInt(st.nextToken()); // 간선의 다른 정덤
graph.get(u).add(v);
graph.get(v).add(u);
}
br.close();
for (int i = 0; i <= N; i++) {
// 인접 정점은 오름차순으로 방문
graph.get(i).sort(Collections.reverseOrder());
}
/** dfs **/
// 노드를 저장 할 stack
Stack<Integer> stack = new Stack<>();
stack.push(start);
// 방문 순서를 저장할 배열
int[] visitOrder = new int[N + 1];
// 방문 여부를 저장 할 배열
boolean[] isVisited = new boolean[N + 1];
// 순서는 1부터 시작
int order = 1;
while (!stack.isEmpty()) {
int vertex = stack.pop();
// 방문하지 않았다면 방문
if (!isVisited[vertex]) {
isVisited[vertex] = true;
visitOrder[vertex] = order++;
for (int i = 0; i < graph.get(vertex).size(); i++) {
int next = graph.get(vertex).get(i);
// 방문 한 적이 없는 노드 탐색
if (!isVisited[next]) {
stack.push(next);
}
}
}
}
/** 출력 **/
StringBuilder sb = new StringBuilder();
// 1부터 시작이므로 기본 for 문 사용
for (int i = 1; i <= N; i++) {
sb.append(visitOrder[i]).append("\n");
}
System.out.println(sb);
}
}
-
기존에는 오름차순 정렬 되어있어 stack 사용 시 내림차순으로 저장됨
- 정렬을 내림차순으로 변경
- for문을 역 순으로 탐색
- for문을 역 순으로 도는 것이 메모리 및 시간 측면에서 유리함
- 가독성 측면에서 향상된 for문을 쓰는 것이 더 좋을 수도 있음 -> 취향에 따라 선택 하면 될 듯 함
-
기존에는 탐색 시에 방문 한 것으로 로직이 짜여 있었다. -> 방문 시에 변경 되도록
visited[next] = true;를stack.pop()다음에 배치 한 결과 중복으로 탐색이 일어나는 경우 여러번 방문함 ->if (!visited[next])를 방문 할 때 확인하는 것으로 수정 ->if (!visited[next])가 중복 되니까 두번째 if문을 제거해봄 -> 메모리 사용량은 증가, 시간은 감소 다만 변화가 미비함 -> 가독성 측면에선 중복을 제거하는 것이 낫다고 보여짐