[백준] 알고리즘 분류(그래프 탐색,JAVA)11403번, 경로 찾기

문제 링크

11403번: 경로 찾기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 가중치가 없는 방향 그래프가 주어집니다.

2. 각 정점에서 다른 정점을 방문할 수 여부를 배열 형태의 결과로 출력합니다.

3. 1은 방문 가능 , 0은 방문 불가능을 표현하는 것입니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 그래프를 탐색하여 각 정점이 다른 정점을 방문하는지 탐색합니다.

 

3. 방문 여부를 배열 형태의 결과로 출력합니다.

 

 

 

저는 처음에 각 정점에서 BFS 탐색을 통해서 다른 정점에 방문확인을 진행하여 해결하였습니다.

 

다른 사람들의 코드를 확인해보니 플로이드-워셜 알고리즘을 이용하여 구하는 것을 보고 코드를 작성해서 비교를 해보았습니다.

 

플로이드-워셜이 근소한 차이로 시간복잡도가 좋음을 확인하고 BFS로 작성한 코드는 간단한 주석으로만 표현해서 공유하겠습니다.

BFS 코드

import java.io.*;
import java.util.*;

public class Main {
    //그래프 방향 간선 저장 리스트
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i=0;i<N;i++)
            graph.add(new ArrayList<>());
        int[][] answer = new int[N][N];
        //그래프 방향 간선 저장
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<N;j++) {
                int n = Integer.parseInt(st.nextToken());
                if(n == 1)
                    graph.get(i).add(j);
            }
        }
        //각 정점에서 BFS 탐색 진행
        for(int i=0;i<N;i++)
            bfs(i, answer, N);

        //각 정점 방문 확인 배열의 형태 BufferdWriter 저장
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++)
                bw.write(answer[i][j] + " " );
            bw.newLine();
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS 탐색 진행하여 방문 확인하는 함수
    public static void bfs(int start, int[][] answer, int N) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[N];	//방문 확인 배열
        q.add(start);		//기준 정점 Queue 저장
        //탐색 진행
        while(!q.isEmpty()) {
            int cur = q.poll();
            //간선 탐색!
            for(int next : graph.get(cur)) {
                if(!visited[next]) {
                    visited[next]= true;
                    answer[start][next] = 1;
                    q.add(next);
                }
            }
        }
    }
}

 

플로이드-워셜 탐색!

 

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전

3중 For문을 통해서 "시작 정점 ▶ 중간 정점 ▶ 도착 정점"으로 그래프를 탐색합니다.

 

시작 정점 ▶ 중간 정점 : 시작 정점은 중간 정점을 방문!

중간 정점 ▶ 도착 정점 : 중간 정점은 도착 정점 방문!, 시작 정점은 도착 간선 추가!

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 3

0 1 0
0 0 1
1 0 0

 

2. 그래프를 탐색하여 각 정점이 다른 정점을 방문하는지 탐색합니다.

 

플로이드-워셜 탐색 진행!

 

시작 정점 : 1

중간 정점 : 2

도착 정점 : 3

시작 정점 : 2

중간 정점 : 3

도착 정점 : 1

시작 정점 : 3

중간 정점 : 1

도착 정점 : 2

3. 방문 여부를 배열 형태의 결과로 출력합니다.

 

1 ▶ 2

2 ▶ 3

 

2 ▶ 3

3 ▶ 1

 

3 ▶ 1

1 ▶ 3

 

1 1 1

 

1 1 1

 

1 1 1

결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 그래프 간선 정보를 띄어쓰기 기준 나누었습니다.
• 플로이드-워셜 탐색을 진행하여 각 정점 방문 확인합니다.
• 각 정점에서 다른 정점 방문확인을 배열 행태의 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과코드

 

import java.io.*;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[][] graph = new int[N][N];	//그래프 정보 저장 배열
        int[][] answer = new int[N][N];	//방문 여부 저장 배열
        //그래프 정보 저장
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<N;j++)
                graph[i][j] =  Integer.parseInt(st.nextToken());
        }
        //플로이드-워셜 탐색!
        for(int i=0;i<N;i++){		//중간 정점
            for(int j=0;j<N;j++){		//시작 정점
                if(graph[j][i] == 0)
                    continue;
                answer[j][i] = 1;		//시작 ▶ 중간
                for(int s = 0;s<N;s++) {		//도착 정점
                    if(graph[i][s] ==0)
                        continue;
                    graph[j][s] = 1;	//방문 간선 추가!
                    answer[j][s] = 1;	//중간 ▶ 도착
                }
            }
        }
        //방문 여부 저장 배열 BufferedWriter 저장
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++)
                bw.write(answer[i][j] + " " );
            bw.newLine();
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}