이것저것 개발 블로그

https://www.acmicpc.net/problem/11403

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_BJ_11403_경로찾기 {
    static int[][] adj;
    static int n;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        adj = new int[n][n];
        int[][] ans = new int[n][n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                adj[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(route(i, j))
                    ans[i][j] = 1;
                else
                    ans[i][j] = 0;
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                sb.append(ans[i][j]+" ");
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }//main
    private static boolean route(int start, int end){
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start);
//        visited[start] = true;

        while(!q.isEmpty()){
            int cur = q.poll();
            for(int i=0; i<n; i++){
                if(adj[cur][i]==1 && !visited[i]){
                    q.add(i);
                    visited[i] = true;
                }
            }
        }

        if(visited[end])
            return true;
        return false;
    }//route
}

이 문제가 플로이드-워셜 문제인걸 풀고 나서 알았다...

다시 공부해서 올려야징

나는 플로이드로 풀진 않았고, bfs랑 비슷한 논리를 사용해서 했다.

이때, 주의할점은 start == end 일 수 있으므로, 큐에 처음 넣을 때 방문처리를 하지 않아야 한다.

또한 queue에서 꺼낸 값 cur이 end와 같다해서 바로 true를 리턴하면 안된다...

처음엔 당연히 출발==도착이면 방문할 수 있을줄 알았다ㅋㅋㅋ

풀이2) 플로이드-워셜 알고리즘

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_BJ_11403_경로찾기 {
    static int[][] adj;
    static int n;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        adj = new int[n][n];
        int[][] ans = new int[n][n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                adj[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //단순히 가는 것만 체크
        for(int k=0; k<n; k++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(adj[i][k] == 1 & adj[k][j]==1)
                        adj[i][j] = 1;
                }
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                System.out.print(adj[i][j]+" ");
            }
            System.out.println();
        }

    }//main
}

이 문제는 플로이드 워셜로 풀면 훨씬 시간이 단축된다.

애초에 간선에 가중치도 없었고, 문제 자체도 연결 되었는지 아닌지만 파악하면 되기 때문!

따라서 adj[i][k] == 1 && adj[k][j]==1의 조건만 있으면 된다.

플로이드-워셜 간단 정리

• 모든 정점에서 모든 정점까지의 최단 거리를 구할 때 사용
• 음수 사이클이 없어야함
• 인접행렬 이용
  • 본인과 본인의 거리는 최소 0이라고 판단
  • 본인과 연결되지 않은 정점은 최대로 넣어줌
• 차례대로 정점을 1개 거치고,,, 2개 거치고,,, n개를 거치는 경우가 가능함. 
  • 즉, 바로 연결된 정점을 가느냐 vs k 정점을 거쳐서 가느냐(이것 또한 계속 갱신된것)
  • adj[i][j] = Math.min(adj[i][j], adj[i][k]+adj[k][j])와 같음

참고한 블로그는 다음과 같다.

https://sskl660.tistory.com/61