[백준] 경로 찾기 - SILVER I 11403번
접근
- bfs
- 플로이드-워셜 (Floyd-Warshall)
풀이
가중치 없는 방향 그래프에서 한 정점에서 다른 정점으로 갈 수 있는 경로가 있는지 없는지 구하는 문제이다. 이 문제도 어김없이 문제를 해석하고 이해하는 게 참 힘들었던 문제이다. 프로그래머스라면 그림이나 예제의 결과가 왜 저렇게 나오는지 해석한 내용이 있어 그걸 보면 바로 이해하고 풀이를 시작할 수 있지만 백준은 역시나 설명조차 애매모호하게 적어놓고 왜 저런 답이 나오는지 풀이도 없어 매번 문제 이해에서 시간을 다 잡아먹는 거 같다.
그래서 문제 설명을 좀 해보자면 이 문제에서 정점들은 방향이 존재하는 그래프를 그리고 있다. 1 -> 2 로만 정점이 연결되어 있다면 1번 정점에서는 2번 정점으로 이동할 수 있지만 2 -> 1의 경우는 불가능한 것이다. 그렇게 연결된 정점들을 통해서 다른 정점으로 이동이 가능한지를 구하는 것인데 요구 출력이 2차원 배열을 출력한 형태로 나와있어 처음에 이해가 잘 가지 않았다. 이 문제가 요구하는 출력은 만약 N의 값이 3일 때 정점은 1,2,3 3개가 존재하고 첫 번째 줄에는 정점 1에서 출발해 정점 1로, 1에서 출발해 정점 2로, 1에서 출발해 정점 3으로 도달이 가능한지 출력하는 것이고 다음 줄에는 정점 2에서 시작한 2 -> 1, 2 -> 2, 2 -> 3의 가능 여부 그다음은 정점 3에서 시작해 가능 여부를 출력하는 것으로 각 정점에서 다른 모든 정점을 도달할 수 있는 것인지 구해 출력하는 것이다.
예제 입력 1번을 살펴보면
예제 입력 1번
3
0 1 0
0 0 1
1 0 0
정점 1, 2, 3
연결 정보
1 -> 2
2 -> 3
3 -> 1정점 1,2,3에 대해 연결된 정보는 저렇고 정점을 타고 들어가며 다른 정점에 도착이 가능한지 구하는 것이다.
출발 : 1, 도착 : 1
1 -> 2 -> 3 -> 1 도달 가능
출발 : 1, 도착 : 2
1 -> 2 도달 가능
출발 : 1, 도착 : 3
1 -> 2 -> 3 도달 가능도달이 가능하면 1을 출력하고 불가능하면 0을 출력하는 문제이다. 정점과 도달이 가능한지 체크하라하면 생각나는 알고리즘이 있다.
private static class Vertex {
private final int index;
private final List<Vertex> linkedVertex;
public Vertex(int index) {
this.index = index;
this.linkedVertex = new ArrayList<>();
}
}바로 bfs로 큐를 사용해 구현하기 위해 연결된 정점들을 가지는 클래스를 만들어 주었다. 정점 클래스는 해당 정점의 인덱스를 나타내는 변수와 연결된 정점들을 가지는 리스트로 구성되었다. 연결된 정점 리스트는 생성자에서 빈 리스트를 생성하여 가지고 있게 만들어 주었다.
int N = Integer.parseInt(br.readLine());
List<Vertex> vertexes = new ArrayList<>();
for (int i = 0; i < N; i++) {
vertexes.add(new Vertex(i));
}
for (int i = 0; i < N; i++) {
String[] input = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
int num = Integer.parseInt(input[j]);
if (num == 1) {
vertexes.get(i).linkedVertex.add(vertexes.get(j));
}
}
}정점들의 리스트를 만들고 총 정점의 개수만큼 리스트에 추가해 주었다. 연결 정보를 통해 각 정점들을 연결해 주었다.
한 정점이 다른 여러개의 정점들과 연결이 될 수 있기 때문에 정점 객체 내 리스트로 연결된 정점들을 관리한다.
for (int i = 0; i < N; i++) {
bfs(vertexes, i, N, bw);
bw.write("\n");
}모든 정점을 순회하며 bfs를 실행해 준다.
private static void bfs(List<Vertex> vertexes, int index, int N, BufferedWriter bw) throws IOException {
Queue<Vertex> que = new LinkedList<>();
que.offer(vertexes.get(index));
boolean[] isVisited = new boolean[N];정점 리스트에서 순서에 해당하는 정점을 꺼내 큐에 넣고 시작 정점으로 설정한다. 방문체크 배열을 통해 도달할 수 있는지를 확인하게 된다. 그리고 bfs나 탐색을 수행할 때 보통 시작점 방문을 true로 체크하는데 이 문제의 경우 정점 1에서 정점 1로 간다고 할 때 출발지와 도착지가 같으니 가능한 경로라 생각할 수 있는데 정점 1에서 시작해 다른 정점들을 거쳐 다시 1로 돌아올 수 있는 경우에 가능한 경로가 되고 다시 정점 1로 돌아오지 못한다면 도달 불가능한 경로가 되기 때문에 이 문제는 시작점 방문 체크를 하면 안 되는 경우이다.
while (!que.isEmpty()) {
Vertex vertex = que.poll();
List<Vertex> linkedVertex = vertex.linkedVertex;
for (Vertex lv : linkedVertex) {
if (isVisited[lv.index]) {
continue;
}
que.offer(lv);
isVisited[lv.index] = true;
}
}bfs를 수행하게 되는데 해당 정점의 연결된 정점들을 방문하지 않았다면 다음 위치로 큐에 추가하게 된다.
for (boolean b : isVisited) {
if (b) {
bw.write("1 ");
} else {
bw.write("0 ");
}
}수행이 끝났다면 방문체크 배열을 순회하여 방문되었던 곳은 가능한 경로로 1을 출력하고 방문되지 않았던 곳은 도달이 불가능한 곳이기 때문에 0을 출력한다.
플로이드-워셜 알고리즘 (Floyd-Warshall)
플로이드-워셜 알고리즘은 가중치가 있는 그래프에서 모든 정점 쌍 간의 최단 경로를 찾기 위해 사용되는 알고리즘으로 동적 프로그래밍을 기반으로 한 방식이다. 만약 정점 i와 정점 j 사이의 간선이 있다면 그 간선의 가중치로 초기화하고 간선이 없다면 무한대로 초기화한다. 2차원 배열을 사용하는 방식으로 연산 수행이 끝나게 되면 문제의 요구 출력과 동일한 형태 배열을 가지게 된다. 현재 문제는 가중치가 없는 그래프로 배열의 인덱스에 가중치 대신 1로 초기화를 해주면 한 번에 요구 출력을 가진 2차원 배열을 만들 수 있다.
int N = Integer.parseInt(br.readLine());
int[][] graph = new int[N][N];
for (int i = 0; i < N; i++) {
graph[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}우선 2차원 배열에 정점들의 연결 정보를 다 넣어준다.
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (graph[i][k] == 1 && graph[k][j] == 1) {
graph[i][j] = 1;
}
}
}
}2차원 그래프가 만들어지는 코드이다. 이 알고리즘은 기본적으로 정점의 개수의 3 중첩으로 이루어진 방법이기 때문에 O(N x N x N)의 시간 복잡도로 정점의 개수가 많아질수록 bfs보다 효율이 훨씬 떨어지지만 가중치가 있는 그래프에서 사용 가능하다는 게 장점이다. k를 기준으로 각 정점에 연결 정보를 확인하여 그래프의 연결 정보를 매핑하게 되는데 i에서 k를 거쳐 j로 가는 경로가 존재하는지 체크하는 과정이다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
bw.write(graph[i][j] + " ");
}
bw.write("\n");
}그리고 완성된 그래프를 출력하면 요구하는 결과가 나오게 된다.
이 문제의 N의 범위는 100까지로 bfs와 큰 성능 차이는 없지만 정점의 수가 더 많아지면 bfs에 비해 확연히 느려지게 될 것이다. 물론 가중치가 없는 그래프를 기준으로 한 얘기로 가중치가 있는 그래프를 위해 알아두면 좋을 것이다.
전체 코드
BFS
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Main {
private static class Vertex {
private final int index;
private final List<Vertex> linkedVertex;
public Vertex(int index) {
this.index = index;
this.linkedVertex = new ArrayList<>();
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
List<Vertex> vertexes = new ArrayList<>();
for (int i = 0; i < N; i++) {
vertexes.add(new Vertex(i));
}
for (int i = 0; i < N; i++) {
String[] input = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
int num = Integer.parseInt(input[j]);
if (num == 1) {
vertexes.get(i).linkedVertex.add(vertexes.get(j));
}
}
}
for (int i = 0; i < N; i++) {
bfs(vertexes, i, N, bw);
bw.write("\n");
}
bw.flush();
bw.close();
br.close();
}
private static void bfs(List<Vertex> vertexes, int index, int N, BufferedWriter bw) throws IOException {
Queue<Vertex> que = new LinkedList<>();
que.offer(vertexes.get(index));
boolean[] isVisited = new boolean[N];
while (!que.isEmpty()) {
Vertex vertex = que.poll();
List<Vertex> linkedVertex = vertex.linkedVertex;
for (Vertex lv : linkedVertex) {
if (isVisited[lv.index]) {
continue;
}
que.offer(lv);
isVisited[lv.index] = true;
}
}
for (boolean b : isVisited) {
if (b) {
bw.write("1 ");
} else {
bw.write("0 ");
}
}
}
}
플로이드-워셜
import java.io.*;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[][] graph = new int[N][N];
for (int i = 0; i < N; i++) {
graph[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (graph[i][k] == 1 && graph[k][j] == 1) {
graph[i][j] = 1;
}
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
bw.write(graph[i][j] + " ");
}
bw.write("\n");
}
bw.flush();
bw.close();
br.close();
}
}'알고리즘 > 코딩테스트-백준' 카테고리의 다른 글
| [백준] 적록색약 JAVA (0) | 2024.09.30 |
|---|---|
| [백준] 토마토 JAVA (0) | 2024.09.29 |
| [백준] 카잉 달력 JAVA (0) | 2024.09.27 |
| [백준] 단지번호 붙이기 JAVA (0) | 2024.09.26 |
| [백준] 숨바꼭질 JAVA (1) | 2024.09.25 |