[Softeer] 출퇴근길 JS (역방향 간선 그래프, dfs)

https://softeer.ai/practice/6248

 

 

출근길, 퇴근길에 모두 포함되는 정점을 구해야한다

 

밑의 조건을 모두 만족하는 경우 출퇴근길에 모두 존재한다고 볼 수 있다.

출근길 (집이랑 연결된) && 출근길 (회사와 연결된) && 퇴근길 (회사와 연결된) && 퇴근길 (집과 연결된)

 

출근길

집을 시작으로 dfs를 돌려 집에서 이동가능한 모든 정점을 구할 수 있다. fromHome

회사에서 역방향으로 dfs를 돌리면 회사에 도달 할 수 있는 정점을 구할 수 있다 toWork

 

퇴근길

회사를 시작으로 dfs를 돌려 회사에서 이동가능한 모든 정점을 구한다. fromWork

역방향 간선 상, 집에서 dfs를 돌려 집에 도달 할 수 있는 정점을 구한다 toHome

 

adj, adjR를 통해 한 정점에서 이동할 수 있는 정점을 이차배열로 정리를 한다.

 

위 4상황마다 방문한 노드를 체크하는 배열을 갖고 dfs를 돌린다.

 

 

단, 주의할 점이 있다.

출근길에 회사는 1번만 마지막에 등장한다. 즉 회사에 도착하면 dfs를 멈춘다

퇴근길에 집은 1번만 마지막에 등장한다. 즉 집에 도착하면 dfs를 멈춘다.

 

 

const readline = require('readline');
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
});

const lines = [];

// input
rl.on('line', input => {
    lines.push(input.split(' ').map(e => parseInt(e)))
})
rl.on('close', () => {
    const [vertexCount, edgeCount] = lines.shift();
    const [house, work] = lines.pop();
    // 이차배열로 점마다 adj정리
    const adj = Array.from({length: vertexCount+1}, () => []);
    const adjR = Array.from({length: vertexCount+1}, () => []); // 역방향
    lines.forEach(([from, to]) => {
        adj[from].push(to);
        adjR[to].push(from);
    })
    // 집에서 출발가능한 점들
    const fromHouse = Array.from({length: vertexCount+1}, () => 0);
    fromHouse[work] = 1; // 회사에 도착하면 멈춘다
    dfs(house, adj, fromHouse);

    // 회사에 도착가능한 점들
    const toWork = Array.from({length: vertexCount+1}, () => 0);
    dfs(work, adjR, toWork);

    // 회사에서 출발가능한 점들
    const fromWork = Array.from({length: vertexCount+1}, () => 0);
    fromWork[house] = 1;
    dfs(work, adj, fromWork);

    // 집에 도착가능한 점들
    const toHouse = Array.from({length: vertexCount+1}, () => 0);
    dfs(house, adjR, toHouse);
    

    let answer = 0;
    for (let i = 1; i <= vertexCount+1; i++) {
        if (fromHouse[i] === 1 && fromWork[i] === 1 && toHouse[i] === 1 && toWork[i] === 1) {
            answer++;
        }
    }
    console.log(answer-2); // 집과 직장을 제외
    
    process.exit();
})
// [이어진곳 모두 방문] 현재노드, 방향, 방문한 흔적 배열
function dfs(curr, adj, visited) {
    // 이미 방문했으면 또 방문하지 않는다
    if (visited[curr] === 1) return;
    visited[curr] = 1; // 방문표시
    // 다음으로 연결된 노드를 방문한다.
    for (const neighbor of adj[curr]) {
        dfs(neighbor, adj, visited);
    }
    // return;
}

 

 

 

 

https://www.youtube.com/watch?v=PAihI2CGr-M

 

 

 

 

https://velog.io/@wp29dud/%EC%B6%9C%ED%87%B4%EA%B7%BC%EA%B8%B8-%ED%92%80%EC%96%B4-%EB%B4%84

출퇴근길 풀어 봄

 

https://stritegdc.tistory.com/363

[sof] 소프티어 <인증평가(6차) 기출> 출퇴근길 - DFS

 

 

 

31-2부터 틀렸다. 문제가 뭘까