[Java] 백준 11403. 경로 찾기

➡️문제 링크

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

 

💡아이디어

한 번에 문제가 이해되지 않았다

뭔 말이야..? 싶어 다시 차근차근 읽어보니

인접그래프를 인접행렬로 표현해 (하나의 정점 -> 모든 정점 )*n 되는지를 묻는 문제였다

 

 

 

 

✏️문제 풀이

1. bfs - 성공

그래프 탐색인데 어떻게 해야할까 고민하다 일단, 0 ~ N-1 까지 행을 기준으로 돌면서 bfs를 진행했다.

여기서 포인트는 양방향 그래프가 아니다 보니까, 정점을 거치면서 도달할 수 있는지 여부를 판단하는게 중요했다.

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int [][] graph = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			StringTokenizer 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++) {
			Queue<int []> que = new LinkedList<>();
			for(int j = 0; j < N; j++) {
				if(graph[i][j] == 1) {
					que.add(new int [] {j, i});
				}
			}
			
			while(!que.isEmpty()) {
				int [] point = que.poll();
				int x = point[0];
				int y = point[1];
				for(int k = 0; k < N; k++) {
					if(graph[x][k] == 1) {
						if(graph[i][k] == 0) {
							que.add(new int[] {k, x});
							graph[i][k] = 1;
						}
					}
				}
			}
		}
		
		// 출력
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				sb.append(graph[i][j]+" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);

	}

}

 

 

2. 플로이드 워셜 - 성공

문제의 알고리즘 유형을 확인해보니 플로이드 워셜이 있어 뭔가 그렇게 풀어도 되는 것 같기도하고..?라는 생각이들어다른 사람들의 풀이를 보는데 대부분 플로이드 워셜을 이용해 풀었다내 풀이는 i에서 출발해서 방문할 수 있는 정점을 체크하는 것이고플로이드 워셜은 모든 (i, j)에 대해 경유지 k를 쳐서 갈 수 있는지를 체크하는 것이다

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int [][] graph = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 모든 i, j에 대해 k 거쳐서 갈 수 있는지
		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;
					}
				}
			}
		}
		
		// 출력
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				sb.append(graph[i][j]+" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);

	}

}