백준 11403 경로 찾기 JAVA

 

문제 : 경로 찾기

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

난이도 : 실버 1

 

💻 풀이 

1. BFS를 이용한 그래프로 풀었다. 

 

2. 만약 (1,2) (2,3) (3,4) (4,5)  가 인접행렬이면

graph[1][2]=graph[1][3]=graph[1][4]=graph[1][5] 다. 

 

3. 2차원 배열로 풀시에는 너무 많은 반복문이 돌아가므로, 

TreeMap과 ArrayList 를 이용하여 인접행렬을 담아주었다. 

* 양방향 그래프가 아님을 신경써서 넣어줘야한다. 

** TreeMap을 이용한 이유는 get() 함수 썼을 때 O(log N)으로 HashMap이나, ArrayList 의 O(1)을 쓰는것이 더 낫지만, 

사용법에 익숙해지기 위해서 사용했음! 이글을 보시는 분들이라면,, HashMap 같이 빠른 Collection Map을 쓰세여 

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//초기화 선언. 
int n = Integer.parseInt(br.readLine());
		
TreeMap<Integer, ArrayList<Integer>> tm = new TreeMap<>();
for (int i = 0; i < n; i++) {
	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
	for (int j = 0; j < n; j++) {
		if (st.nextToken().equals("1")) {
			if (tm.get(i) != null) {
				ArrayList<Integer> list = tm.get(i);
				list.add(j);
				tm.put(i, list);
			} else {
				ArrayList<Integer> list = new ArrayList<>();
				list.add(j);
				tm.put(i, list);
			}					
		}
	}
}

 

4. 모든 정점을 다 봐야하므로, for 문을 통해 돌려주었다. 

 

5. 62%에서 계속 틀렸습니다가 떠서 고민해보니, 

Queue를 넣어서 ArrayList 를 계속 꺼내줄때 경로가 아예 없는 정점이 있다면, 

While문을 이용하여 Queue에서 다음 정점을 꺼내어 ArrayList가 있는 정점을 찾았다. 

 

int[][] graph = new int[n][n];	
for (int p = 0; p < n; p++) {
	ArrayList<Integer> list = tm.get(p);
	if (list == null) continue;
			
	Queue<Integer> qu = new LinkedList<>();
	boolean[] vis = new boolean[n];
	boolean ok = true;
	while (ok) {				
		for (int l : list) {
			graph[p][l] = 1;
			/* 방문하지 않는 정점만 queue에 추가한다. */
			if (!vis[l])
				qu.add(l);
			vis[l] = true;
		}
				
		if (qu.isEmpty()) break;
				
		/* list가 null이면 queue에서 다른 정점을 찾아 꺼내준다. */				
		list = tm.get(qu.poll());
		while (list == null) {
			if (qu.isEmpty()) {
				ok = false;
				break;
			}
			list = tm.get(qu.poll());
		}
	}
}

 

✨ 전체 코드 

 

import java.io.*;
import java.util.*;
import java.util.Map.Entry;


public class Main {
	
	public static void main(String[] args) throws Exception {		
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//초기화 선언. 
		int n = Integer.parseInt(br.readLine());
		
		TreeMap<Integer, ArrayList<Integer>> tm = new TreeMap<>();
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < n; j++) {
				if (st.nextToken().equals("1")) {
					if (tm.get(i) != null) {
						ArrayList<Integer> list = tm.get(i);
						list.add(j);
						tm.put(i, list);
					} else {
						ArrayList<Integer> list = new ArrayList<>();
						list.add(j);
						tm.put(i, list);
					}					
				}
			}
		}
		
		int[][] graph = new int[n][n];	
		for (int p = 0; p < n; p++) {
			ArrayList<Integer> list = tm.get(p);
			if (list == null) continue;
			
			Queue<Integer> qu = new LinkedList<>();
			boolean[] vis = new boolean[n];
			boolean ok = true;
			while (ok) {				
				for (int l : list) {
					graph[p][l] = 1;
					/* 방문하지 않는 정점만 queue에 추가한다. */
					if (!vis[l])
						qu.add(l);
					vis[l] = true;
				}
				
				if (qu.isEmpty()) break;
				
				/* list가 null이면 queue에서 다른 정점을 찾아 꺼내준다. */				
				list = tm.get(qu.poll());
				while (list == null) {
					if (qu.isEmpty()) {
						ok = false;
						break;
					}
					list = tm.get(qu.poll());
				}
			}
		}
		
		
		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);
	}
}