[백준] 11403. 경로 찾기 풀이

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

 

입력된 간선 정보를 바탕으로 탐색을 진행하며 각각의 노드들 사이에 상대방을 탐색할 수 있는지를 점검해야하는 문제.

 

"i번째 줄에 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고"

-> i에서 j를 탐색할 수 있으므로 해당 위치에서 탐색을 시작하지 않아도 됨.

 

결국 i번째 줄의 j번째 숫자가 0인 경우에 i에서 탐색을 진행하여 j까지 탐색이 가능한지 확인하여야 하고, 그 과정에서 시간 단축을 위해 시작 지점에서 탐색한 지점, 현재 지점에서 탐색한 지점으로 경로가 있음을 저장할 수 있다.

 

이때 순환형 그래프에 걸릴 경우 무한반복에 걸릴 수 있으므로 지나온 위치를 다시 가지 않도록 하고(check배열 혹은 리스트를 사용함.)

다른 위치에서 탐색을 진행할 때 이전 위치에서 탐색한 지점을 다시 지나야 하는 경우(예를 들어 순환형 그래프에서 자기 자신을 탐색할 수 있는지 확인해야 하는 경우)가 있으므로 지나온 위치를 저장한 내용을 초기화 하였다.

 

결과적으로 i에서 j로 탐색이 가능하면 i번째 줄의 j번째 숫자에 1을 저장.

탐색을 모두 마치면 결과 출력.

 

---

C

#include <stdio.h>

int res[101][101];
int edge[101][101];
int check[101];

void append(int idx, int v){
    for(int i = 0; i < 101; i++){
        if(edge[idx][i] == 0) {
            edge[idx][i] = v;
            break;
        }
    }
}

void checkInit(int len){
    for(int i = 1; i <= len; i++) check[i] = 0;
}

void DFS(int v, int start, int goal, int depth){
    if(v == goal && depth > 0){
        res[start][goal] = 1;
        return;
    }
    if(check[v]) return;
    check[v] = 1;

    for(int i = 0; i < 101; i++){
        if(edge[v][i] == 0) break;
        res[start][edge[v][i]] = 1; // 처음노드 -> 탐색한 노드
        res[v][edge[v][i]] = 1; // 현재노드 -> 탐색한 노드
        DFS(edge[v][i], start, goal, depth+1);
    }
}

int main() {
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            scanf("%d", &res[i][j]);
            if(res[i][j]) append(i, j);
    }}

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(res[i][j] == 0){
                checkInit(n);
                DFS(i, i, j, 0);
            }
    }}

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) printf("%d ", res[i][j]);
        printf("\n");
    }
}

---

Python

from collections import deque
import sys
sys.setrecursionlimit(10**6)

def DFS(v, start, goal, depth):
    global res; global edge
    if v == goal and depth > 0:
        res[start][goal] = 1
        return
    if check[v] == True: return
    check[v] = True

    for i in edge[v]:
        res[start][i] = 1; res[v][i] = 1
        DFS(i, start, goal, depth+1)

n = int(input())
edge = [[] for _ in range(n)]
res = [[] for _ in range(n)]
for i in range(n):
    res[i] = list(map(int, input().split()))
    for j in range(n):
        if res[i][j] == 1:
            edge[i].append(j)

for i in range(n):
    for j in range(n):
        if res[i][j] == 0:
            check = [False for _ in range(n)]
            DFS(i, i, j, 0)
for i in range(n):
    for j in range(n):
        print(res[i][j], end=' ')
    print()