[문제 이름 : 경로 찾기 (백준 11403, S1)]
문제 url : https://www.acmicpc.net/problem/11403
내가 작성한 코드는 아래와 같다.
import java.util.*;
import java.io.*;
public class Main {
static ArrayList<Integer>[] A;
static int num;
static int[][] answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
num = Integer.parseInt(br.readLine());
A = new ArrayList[num];
answer = new int[num][num];
for (int i = 0; i < num; i++) {
A[i] = new ArrayList<>();
}
for (int i = 0; i < num; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < num; j++) {
int cur = Integer.parseInt(st.nextToken());
// 방향 그래프 성립
if (cur == 1) {
A[i].add(j);
}
}
}
for (int i = 0; i < num; i++) {
boolean[] visited = new boolean[num];
// Node 탐색 - DFS
DFS(i, i, visited);
// BFS
// BFS(i, num);
}
// 결과 출력
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
System.out.print(answer[i][j] + " ");
}
System.out.println();
}
}
static void DFS(int start, int node, boolean[] visited) {
for (int next : A[node]) {
if (!visited[next]) {
visited[next] = true;
answer[start][next] = 1;
DFS(start, next, visited);
}
}
}
static void BFS(int start, int num) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[num];
queue.add(start);
while (!queue.isEmpty()) {
int current = queue.poll();
for (int next : A[current]) {
if (!visited[next]) {
visited[next] = true;
answer[start][next] = 1;
queue.add(next);
}
}
}
}
}
[풀이 과정] - (풀이 시간: 1시간)
모든 경로를 탐색해야 하므로, DFS로 먼저 풀이해 보았다. 방문하지 않은 노드는 1로 업데이트 해주면서, 결과를 출력해준다. BFS 풀이 방법도 이와 유사하다. 단지 DFS/BFS 차이는 깊이우선/너비우선에 따른 코드 구성 차이에만 있다.
이후, 다른 블로그를 들어가 보니 플로이드-워샬 알고리즘에 대한 내용이 있어, 이를 추가로 적어보고자 한다.
[플로이드-워샬 알고리즘]
이는 그래프의 모든 정점 쌍에 대한 최단 거리를 찾을 때 사용하는 알고리즘이다.
시간복잡도는 O(N^3)으로, 그래프의 모든 노드에 대해 경로를 찾고 갱신하는 과정을 반복한다.
동적계획법을 기반으로, 특정 노드를 거쳐 다른 노드로 가는 경로가 더 짧은지 지속적으로 확인하며 최단 경로를 갱신하는 방식이다.
기본 원리는 아래와 같다.
- 1. 기본 초기화
- 그래프를 인접 행렬로 나타내며, dist[i][j]는 i에서 j로의 경로를 의미한다.
- 만약 직접 연결되어 있지 않다면, Integer.MAX_VALUE로 초기화하고, dist[i][i]는 0으로 설정한다.
- 2. 중간 노드를 고려하여 갱신하기
- 모든 노드 쌍 (i,j)에 대해, k 노드를 경유하여 갈 때 더 짧은 경로가 있는지 확인한다.
- dist[i][j] > dist[i][k] + dist[k][j]인 경우, dist[i][j]를 갱신하여 더 짧은 경로를 저장한다.
- 3. 최종 결과
- 모든 노드 쌍에 대해 최단 경로, 또는 경로 유무를 판별할 수 있다.
이 문제에서는 경로 유뮤만 판별하면 되므로, 경로가 존재하면 1, 존재하지 않으면 0을 저장하는 방식으로 적용하면 된다.
기본 원리 2번을 적용할 때, dist[i][k] == 1 && dist[k][j] == 1 인 경우, dist[i][j]=1로 갱신해주면 된다.
import java.util.*;
import java.io.*;
public class Main {
static int num;
static int[][] dist;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
num = Integer.parseInt(br.readLine());
dist = new int[num][num];
// 입력 처리
for (int i = 0; i < num; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < num; j++) {
dist[i][j] = Integer.parseInt(st.nextToken());
}
}
// 플로이드-워샬 알고리즘
for (int k = 0; k < num; k++) { // 중간 노드
for (int i = 0; i < num; i++) { // 시작 노드
for (int j = 0; j < num; j++) { // 도착 노드
if (dist[i][k] == 1 && dist[k][j] == 1) {
// 경로가 존재하는 경우
dist[i][j] = 1;
}
}
}
}
// 결과 출력
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
System.out.print(dist[i][j] + " ");
}
System.out.println();
}
}
}
내일은 저번주에 봤던 코딩테스트를 복기해볼 예정이다.