백준 224479

깊이우선탐색(DFS) 개념이 중심 해결책이 되는 문제이다.
https://www.acmicpc.net/problem/24479

정점의 갯수 = 5개,
간선의 갯수 = 5개,
시작 정점= 첫번째 정점이라고 한다.
그리고

1번째 정점과 4번째 정점에
1번째 정점과 2번째 정점에
2번째 정점과 3번째 정점에
2번째 정점과 4번째 정점에
3번째 정점과 4번째 정점에
간선이 존재한다고 한다.

이러한 그림으로 그래프를 표현해 보았다.

DFS로 한다고 했을 때, 오름차순으로 그래프를 순회한다고 하면
그래프의 순회순서는..
1번째 그래프 - 2번째 그래프 - 3번쨰 그래프 - 4번째 그래프이다.

이에 맞춰서 자료구조를 이러한 그림으로 표현했다.

여기서 조심해야 할 점은 graph안에 있는 각 배열을 오름차순으로 정렬해야 한다. graph의 요소를 연결리스트가 아닌 배열로 표현한 것도 내장함수로 간단하게 graph의 각 배열을 오름차순으로 정렬할 수 있으니까
graph안의 각 요소를 연결리스트가 아닌 배열로 표현해주었다.

여기까지가 graph를 만드는 작업이고 밑에는 여기까지의 코드이다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\r\n');

[commands,...edges] = input;
//commands = 5 5 1

[numOfVertexes,numOfEdges,rootVertex] = commands.split(' ').map((v)=>+v);
//numOfvertex = 5, numOfEdges = 5, rootVertex = 1이다. 

const graph = Array.from(Array(numOfVertexes), () => new Array());  
//graph=[[],[],[],[],[]] 이다. 

let edgesArr = [];
edges.forEach((v)=>{
    let arr = v.split(' ').map((v)=>+v);
    edgesArr.push(arr);
})
//edgesArr= [[1,4],[1,2],[2,3],[2,4],[3,4]]

edgesArr.forEach((v)=>{
    graph[v[0]-1].push(v[1]);
    graph[v[1]-1].push(v[0]);
})
//graph= [ [ 4, 2 ], [ 1, 3, 4 ], [ 2, 4 ], [ 1, 2, 3 ], [] ]


graph.forEach((v)=>v.sort((a,b)=>a-b));
//graph=[[2,4],[1,3,4],[2,4],[1,2,4],[]]

const visited = Array(numOfVertexes).fill(false); 
// 각 정점의 방문 여부를 저장하는 배열이다. 
// 방문 한 정점은 true, 방문하지 않은 정점은 false로 표시한다.

이제 dfs함수를 구현할 차례이다.
순서도는 이러하다.

빨간 상자부분이 반복되니까 이 부분대로 재귀함수를 짜보았다.

dfs 코드이다.

const dfs = (vertex)=>{
    if(visited[vertex-1]===true){return;}// 이미 방문한 정점이면 return
    visited[vertex-1]=true; // 아니라면 방문
    if(graph[vertex-1].length===0){return;} // 인접한 정점이 없다면 return
    else{ // 인접한 정점이 있다면
        for(let i = 0; i<graph[vertex-1].length; i++){
        // 인접한 정점만큼 하나씩 dfs 함수를 재귀호출한다.
            dfs(graph[vertex-1][i]);
        }
    }
}

결과적으로 여기까지는 문제가 없었다.

하지만 결국 못풀었는데 틀렸던 부분은 여기이다.

const visited_prev = [...visited];
const answer = Array(numOfVertexes).fill(0);

const dfs = (vertex)=>{
    if(visited[vertex-1]===true){return;}// 이미 방문한 정점이면 return
    visited[vertex-1]=true; // 아니라면 방문
    if(graph[vertex-1].length===0){return;} // 인접한 정점이 없다면 return
    else{ // 인접한 정점이 있다면
        j++;
        visited.forEach((v,i)=>{
            if(v!==visited_prev[i]){
                answer[i] = j;
                visited_prev[i]= true;
            }
        })
        for(let i = 0; i<graph[vertex-1].length; i++){
        // 인접한 정점만큼 하나씩 dsf함수 재귀 호출..
            dfs(graph[vertex-1][i]);
        }
    }
}

내가 한 방식은 visited_prev 배열로 visited 배열의 복사본 배열을 하나 만들어 놓고 복사 본 배열을 이용해서 방문할 때마다 원본 visited 배열의 요소와 비교해서 바뀐 정점을 알아낸 뒤 순서를 나타내주는 거였는데
그렇게 하면 시간 초과가 났다.

  j++;
        visited.forEach((v,i)=>{
            if(v!==visited_prev[i]){
                answer[i] = j;
                visited_prev[i]= true;
            }
        })

다른 사람 블로그에 글을 참고해서 이 부분을 고쳤다.
https://prod.velog.io/@bkdragon0228/%EB%B0%B1%EC%A4%80-24479-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-1

const answer = Array(numOfVertexes).fill(0);
const dfs = (vertex)=>{
    if(visited[vertex-1]===true){return;}// 이미 방문한 정점이면 return
    visited[vertex-1]=true; // 아니라면 방문
    answer[vertex-1] = visitOrder;
    visitOrder++; 
    if(graph[vertex-1].length===0){return;} // 인접한 정점이 없다면 return
    else{ 
        for(let i = 0; i<graph[vertex-1].length; i++){// 인접한 정점만큼 하나씩..
            dfs(graph[vertex-1][i]);
        }
    }
}

수정 후 맞은 전체 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

[commands,...edges] = input;
[numOfVertexes,numOfEdges,rootVertex] = commands.split(' ').map((v)=>+v);
const graph = Array.from(Array(numOfVertexes), () => new Array());
const visited = Array(numOfVertexes).fill(false);
const answer = Array(numOfVertexes).fill(0);

let edgesArr = [];
edges.forEach((v)=>{
    let arr = v.split(' ').map((v)=>+v);
    edgesArr.push(arr);
})

edgesArr.forEach((v)=>{
    graph[v[0]-1].push(v[1]);
    graph[v[1]-1].push(v[0]);
})

graph.forEach((v)=>v.sort((a,b)=>a-b));

let visitOrder = 1; // 방문순서

const dfs = (vertex)=>{
    if(visited[vertex-1]===true){return;}// 이미 방문한 정점이면 return
    visited[vertex-1]=true; // 아니라면 방문
    answer[vertex-1] = visitOrder;
    visitOrder++; 
    if(graph[vertex-1].length===0){return;} // 인접한 정점이 없다면 return
    else{ 
        for(let i = 0; i<graph[vertex-1].length; i++){// 인접한 정점만큼 하나씩..
            dfs(graph[vertex-1][i]);
        }
    }
}
dfs(rootVertex);
console.log(answer.join(' '));