백준 11403번 경로 찾기 S1 - 플로이드 위샬, BFS

응 알아.

아오 오래걸렸네

 

오래걸렸다. 순환되는 경우를 고려했는데 생각해보니 필요가 없었다.

단방향 간선이 주어지고, 1->2 갈수있고, 2->3, 3->1 이라면 1에서 1,2,3 모두 갈 수 있게 표기해야하는 문제다.

가보자.

 

플로이드 위셜은 N^3으로 음수가 없는 최단 경로의 가중치를 계산하는데 적합하다.

3중 for문을 사용하여 탐색하고, i에서 j로 갈수 있다면, i -> k , k -> j가 가능한지 판단해서 초기화 해준다.

이 문제는 가중치는 없으나 i에서는 j만 갈 수 있으나 j를 거쳐 k로 가는 방법도 알아야 하므로 사용했다.

 

import java.util.*;
 
public class Main { // 백준 11403번 경로 찾기 S1
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int answer = 0;
        int N = sc.nextInt();
        int[][] arr = new int[N][N];
        int[][] can = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int a = sc.nextInt();
                arr[i][j] = a;
 
            }
        }
        // 1 == i에서 j로 갈수있으려면. i에서 k가 체크되고, k에서 j가 체크 되어야 가능
        // 거쳐가는 지점인 k로 비교를 해야함. 따라서 k i j 순으로 비교
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (arr[i][k] == 1 && arr[k][j] == 1) {
                        arr[i][j] = 1;
                    }
                }
            }
        }
 
    StringBuilder sb = new StringBuilder();for(
    int i = 0;i<N;i++)
    {
        for (int j = 0; j < N; j++) {
            sb.append(arr[i][j]);
            sb.append(" ");
        }
        sb.append("\n");
    }
 
    System.out.println(sb);
 
    }
}

 

애를 먹었다. k i j. 순이 아닌  i j k로 작성했기 때문이다.

 i에서 j로 간다면 i j 와 j k가 갈 수 있는지 판단하는건 당연한데 로직을 잘못 고려했었다.

k의 경로를 기준으로 계산해야 올바르게 체크할 수 있다.

// 1 == i에서 j로 갈수있으려면. i에서 k가 체크되고, k에서 j가 체크 되어야 가능
		// 거쳐가는 지점인 k로 비교를 해야함. 따라서 k i j 순으로 비교
		for (int k = 0; k < N; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (arr[i][k] == 1 && arr[k][j] == 1) {
						arr[i][j] = 1;
					}
				}
			}
		}

 

 

다음으로는 BFS다.

플로이드 위샬이랑 별반 메모리 차이가 없을것 같은데 이러한 유형의 문제를 BFS로 풀지 않았어서 풀어봤다.

고려사항은 어떻게 방문 처리를 할것인가 였다.

숫자 1부터 N까지 하나하나 고려하면서 체크를 해주는 방식을 택했다.

만약 숫자 1에서 k를 갈 수 있다면, k에서 갈 수 있는 방법을 찾아 넣어준다. 방문 체크를 해주면 k는 더이상 고려 안하므로 무한 순환될 일은 없다.

 

로직을 자연어로 정리하면 

 

1. 시작 숫자(start)를 1부터 N까지 하나 하나 탐색한다. can[] 을 숫자마다 초기화한다.

2. start 에서 0부터 k중 1이 있다면, 해당 경로를 큐에 넣어준다.

2-1 해당 k를 체크한다. can[k] = true;

2-2 arr에서 해당 인덱스를 가능하다고 처리한다. arr[i][k] = 1;

N까지 반복한다.

 

import java.util.*;
 
public class Main { // 백준 11403번 경로 찾기 S1 dfs
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int answer = 0;
        int N = sc.nextInt();
        int[][] arr = new int[N][N];
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
 
        for (int i = 0; i < N; i++) {
            boolean[] can = new boolean[N];
            Queue<Integer> que = new LinkedList<>();
            que.add(i);
            while (!que.isEmpty()) {
                int start = que.poll();
                for (int k = 0; k < N; k++) {
                    if (arr[start][k] == 1 && !can[k]) {
                        can[k] = true;
                        arr[i][k] = 1;
                        que.add(k);
                    }
                }
            }
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(arr[i][j]);
                sb.append(" ");
            }
            sb.append("\n");
        }
 
        System.out.println(sb);
 
    }
}

 

숫자 실수에 멘붕이 왔었는데 바로 다른 방식을 사용해보는 연습도 필요하겠다.