[파이썬, Java] 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으로 출력해야 한다.

예제 입력 1 

3

0 1 0

0 0 1

1 0 0

예제 출력 1 

1 1 1

1 1 1

1 1 1

예제 입력 2 

7

0 0 0 1 0 0 0

0 0 0 0 0 0 1

0 0 0 0 0 0 0

0 0 0 0 1 1 0

1 0 0 0 0 0 0

0 0 0 0 0 0 1

0 0 1 0 0 0 0

예제 출력 2 

1 0 1 1 1 1 1

0 0 1 0 0 0 1

0 0 0 0 0 0 0

1 0 1 1 1 1 1

1 0 1 1 1 1 1

0 0 1 0 0 0 1

0 0 1 0 0 0 0

 

 

🦔 나의 풀이

from collections import deque
import sys
input=sys.stdin.readline
N=int(input())      # 정점의 개수
G=[list(map(int, input().split())) for _ in range(N)]
result=[[0]*N for _ in range(N)]
lst=[[] for _ in range(N)]      # 간선 정보

# 간선 정보
for i in range(N) :
    for j in range(N) :
        if G[i][j] == 1 :
            lst[i].append(j)

def bfs(i) :
    q=deque([i])
    while q :
        node=q.popleft()
        for v in lst[node] :
            if not visited[v] :
                visited[v]=1
                q.append(v)
                if not result[i][v] :
                    result[i][v]=1


for i in range(N) :
    visited = [0] * N
    bfs(i)
    print(*result[i])

bfs 풀이

단방향 연결을 한 후 각 정점마다 bfs를 호출했다.

처음에 예제 입력 1만 보고 i==j면 무조건 1로 착각했었다.

i==j가 1인 경우는 i에서 j로 다시 돌아올 수 있는 것이다.

i와 연결 된 정점의 정점들까지 모두 방문한다.

 

 

import sys
input=sys.stdin.readline
N=int(input())      # 정점의 개수
G=[list(map(int, input().split())) for _ in range(N)]
result=[[0]*N for _ in range(N)]
lst=[[] for _ in range(N)]      # 간선 정보

# 간선 정보
for i in range(N) :
    for j in range(N) :
        if G[i][j] == 1 :
            lst[i].append(j)

def dfs(i, v) :
    for node in lst[v] :
        if not result[i][node] :
            result[i][node]=1
            dfs(i, node)


for i in range(N) :
    dfs(i, i)
    print(*result[i])

dfs 풀이

위의 bfs보다 더 빨랐다.

정점 i와 연결된 v노드를 탐색한다.

result[i][node]가 0이면(아직 i에서 node로 갈 수 없음) 재귀호출을 한다.

모든 v 노드들을 탐색했는데 result[i][node]==0인 노드가 없으면 끝난다.

 

 

🐍 다른 사람 풀이

import sys

def sol() :
    input=sys.stdin.readline
    N=int(input())
    node=[[] for i in range(N)]
    for i in range(N) :
        vector=list(map(int, input().split()))
        for j in range(N) :
            if vector[j] == 1 :
                node[i].append(j)
    for i in range(N) :
        print(" ".join(bfs(N, node, i)))

def bfs(N, node, i) :
    queue=[]
    visited=[False]*N
    queue.append(i)
    while len(queue) > 0 :
        v=queue.pop(0)
        for w in node[v] :
            if not visited[w] :
                visited[w]=True
                queue.append(w)
    result=[]
    for check in visited :
        if check :
            result.append("1")
        else :
            result.append("0")
    return result

if __name__ == "__main__" :
    sol()

bfs 풀이

내 풀이랑 크게 다른 점은 없다.

나는 2차원 리스트의 값을 0으로 초기화한 후 경로가 있을 때 1로 변경하도록 만들었다.

위 풀이는 완성된 visited 리스트의 값에 따라서 1 또는 0을 추가해 result를 만들었다.

 

 

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

class Main {
    static int N;
    static int[][] map;
    static boolean[] check;
    static boolean isCycle;

    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        N=Integer.parseInt(br.readLine());
        map=new int[N][N];
        check=new boolean[N];
        q=new int[N*N];
        String str;

        for(int i=0; i<N; i++){
            str=br.readLine();
            // 공백은 건너뛰려고 index+=2만큼 증가
            for(int j=0, index=0; j<N; j++, index+=2){	
                map[i][j]=str.charAt(index)-'0';
            }
        }

        for(int i=0; i<N; i++){
            Arrays.fill(check, false);
            isCycle=false;

            bfs(i);

            for(int j=0; j<N; j++){
                if(i == j){
                    if(isCycle){
                        sb.append(1).append(' ');
                    }else{
                        sb.append(0).append(' ');
                    }
                    continue;
                }
                if(check[j]){
                    sb.append(1).append(' ');
                }else{
                    sb.append(0).append(' ');
                }
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }

    static int[] q;
    static int front, rear, cur;

    private static void bfs(int start) {
        front=rear=-1;

        check[start]=true;
        q[++rear]=start;

        while(front != rear){
            cur=q[++front];
            for(int i=0; i<N; i++){
                if(map[cur][i] == 1){
                    if(!isCycle && i == start){
                        isCycle=true;
                    }
                    if(!check[i]){
                        check[i]=true;
                        q[++rear]=i;
                    }
                }
            }
        }
    }
}

 

흔히 bfs는 deque를 사용하는데 위 코드는 N*N 사이즈의 배열 q에서 인덱스 front, rear로 조작한다.

map[i][j]=str.charAt(index)-'0';는 문자가 정수 타입으로 자동형변환 되어 저장된다.

'0'을 빼주지 않으면 0의 아스키코드 값이 48이 저장된다.

bfs 메소드에서 map[cur][i]==1일 때 i==start와 i != start 두 가지 경우로 나누고 있다.

i==start 부분 없애도 통과는 하지만, 위 풀이가 좀더 빠르다.

 

 

 

문제 출처 👉 백준