[Baekjoon] 11403_경로 찾기

Silver I

문제(출처: https://www.acmicpc.net/problem/11403)

---

<경로 찾기>

문제 

 

가중치 없는 방향 그래프 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으로 출력해야 한다.

 

 

문제 풀이

   - my solution (Python)

import sys
from collections import deque

def bfs(graph, visited, start):
    queue=deque([start])
    result=[] # 경로

    while queue:
        temp=queue.popleft()
        for i in graph[temp]:
            if visited[i]==0:
                queue.append(i)
                visited[i]=1
                result.append(i)
    return result

if __name__=='__main__':
    n=int(input()) # 정점의 개수

    graph={}
    for i in range(n):
        graph[i]=[]

    for i in range(n): # 인접 행렬 : i -> j 경로 표시
        s=list(map(int, sys.stdin.readline().split()))
        for j in range(n):
            if s[j]==1:
                graph[i].append(j)

    answer=[[0]*n for i in range(n)]

    for i in range(n):
        visited = [0] * n # 방문 여부
        result=bfs(graph, visited, i)
        for j in result: # i -> j 경로 존재
            answer[i][j]=1

    for i in answer:
        print(' '.join(map(str,i)))

 

- my solution (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class _11403_경로찾기 {
	static ArrayList<Integer> bfs(HashMap graph, int visited[], int start) {
		Queue<Integer> queue=new LinkedList<>();
		ArrayList<Integer> result=new ArrayList<>(); // 경로
		
		queue.add(start);
		
		while(queue.size()!=0) {
			int temp=queue.poll();
			ArrayList<Integer> x=(ArrayList<Integer>) graph.get(temp);
			for(int i=0; i<x.size(); i++) {
				if(visited[x.get(i)] == 0) {
					queue.add(x.get(i));
					visited[x.get(i)]=1;
					result.add(x.get(i));
				}
			}
		}
		return result;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		
		int n=Integer.parseInt(bf.readLine()); // 정점의 개수
		HashMap<Integer, ArrayList<Integer>> graph=new HashMap<>();
		
		
		for(int i=0; i<n; i++) {
			graph.put(i, new ArrayList<>());
		}
		
		int temp[]=new int[n];
		for(int i=0; i<n; i++) { // 인접 행렬 : i -> j 경로 표시
			String s=bf.readLine();
			for(int j=0; j<n; j++) {
				temp[j]=Integer.parseInt(s.split(" ")[j]);
			}
			for(int j=0; j<n; j++) {
				if(temp[j]==1) {
					ArrayList<Integer> x=graph.get(i);
					x.add(j);
					graph.put(i,x);
				}
			}
		}
		int answer[][]=new int[n][n];
		
		for(int i=0; i<n; i++) {
			int visited[]=new int[n]; // 방문 여부
			ArrayList<Integer> result=bfs(graph,visited,i);
			for(int j=0; j<result.size(); j++) { // i -> j 경로 존재
				answer[i][result.get(j)]=1;
			}
		}
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				System.out.print(answer[i][j]+" ");
			}
			System.out.println();
		}
	}

}

 

주어진 인접 행렬에 따라 i -> j로 연결된 경로를 dict, HashMap으로 정리 후 각 정점에서 bfs를 통하여 간선의 여부를 알아낸다.

 

• bfs ( graph, 방문 여부, 시작 위치)
  : result = 시작 위치에서 갈 수 있는 정점
  : queue가 빌 때까지 반복 -> 제일 처음 값을 pop -> pop 한 값에서 연결된 정점을 순환 -> 아직 방문하지 않았으면 qeuue에 추가 및 방문 check, result에 추가
  : result 반환
  
  
• main
  : n = 정점의 개수
  : graph = 간선 연결
  : 주어진 인접 행렬을 입력받아 i -> j 경로 표시
  : answer = 정답 ( 인접 행렬 형식 )
  : 각 정점에서 함수 호출 후 반환한 값을 활용하여 경로 존재하는 곳 1로 저장
  : answer ( 인접 행렬 ) 출력

---

생각🤔

 

한 번만에 통과하는 건 너무 기분 좋은 일!!!

크게 어렵지 않았던 문제였다.

 

---