백준 11403 - 경로 찾기

백준 11403 - 경로 찾기

나의 코드

const fs = require('fs');
// /dev/stdin
const input = fs.readFileSync('test.txt').toString().trim().split('\n');
const G = parseInt(input[0]);
const link = input.slice(1).map(i => i.trim().split(' ').map(v => +v));

let dic = {};
for (let i = 0; i < G; i++) {
    for(let j = 0; j < G; j++) {
        if(link[i][j] === 1){
            dic[i] ? dic[i].push(j) : dic[i] = [j];
        }   
    }
}

for (let i = 0; i < G; i++) {
	for (let j = 0; j < G; j++) {
        if (dic[i] && Array.from(dic[i]).includes(j)) {
			dfs(i, dic[j]);
        }
    } 
    console.log("====")
}

function dfs (key, values) {
    console.log(values);
    if (values) {
        if(values.length === 1){
            if (link[key][values[0]] === 0) {
                link[key][values[0]] = 1;
                if (dic[values[0]]) dfs(key, dic[values[0]]);
            }
        }
        else{
            values.forEach((v) => {
                link[key][v] = 1;
                dfs(key, dic[v]);
            });
        }
    }
};

answer = link.map(li => li.join(' ').trim());
answer.forEach(v => console.log(v));

답안

const fs = require('fs');
// /dev/stdin
const input = fs.readFileSync('test.txt').toString().trim().split('\n');
const G = parseInt(input[0]);
const graph = input.slice(1).map(i => i.trim().split(' ').map(Number));

let output = [...Array(G)].map(()=>Array(G).fill(0));

const dfs = (node, start, visited) => {
    for(let i = 0; i < G; i++) {
        if(graph[node][i] && !visited[i]){
            visited[i] = true;
            output[start][i] = 1;
            dfs(i,start,visited);
        }
    }
}

for(let i = 0; i < G ; i++){
    const visited = Array(G).fill(false);
    dfs(i,i,visited);
}

output.map(li => li.join(' ').trim()).forEach((v) => console.log(v));