글 읽기 - [node.js] 선배님들 반례 부탁드립니다 ㅠㅠㅠ...

fgstudy 2년 전 0

안녕하세요 선배님들ㅠ 문제가 계속 틀렸다고 떠서 글을 올립니다..

저는 이 문제를 그래프를 구현해서 풀었고, 문제에서 "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문"하라고 하길래 일단 간선들을 전부 연결해준 다음 "Object.values(graph.adjacencyList).map(el => el.sort((a,b) => a-b))"를 해 정렬을 해준다음 답을 구했습니다!

그런데 제가 어디서 잘못 구현한건지 답이 나오질 않아서 ㅠㅠ... 그래서 고수님들께 도움을 구하고자 질문글을 작성하였습니다!
혹시 제가 어느부분에서 놓친걸까요...? 질문글에 있는 반례들을 5페이지까지 넣어주었는데 전부 정답이 나오길래, 혹시 제가 놓친 반례가 있다면 알려주신다면 정말 감사하겠습니다 !!

// 그래프 구현
class Graph{
    constructor(){
        this.adjacencyList = {};
    }
    addVertex(vertex){
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
    addEdge(v1,v2) {
        this.adjacencyList[v1].push(v2);
        this.adjacencyList[v2].push(v1);
    }
    depthFirstSearch(start){
        const result = [];
        const visited = {};
        const adjacencyList = this.adjacencyList;

        (function dfs(vertex){
            if(!vertex) return;
            visited[vertex] = true;
            result.push(vertex);
            adjacencyList[vertex].forEach(neighbor => {
                if(!visited[neighbor]){
                    return dfs(neighbor)
                }
            });
        })(start);

        return result;
    }
    breadthFirstSearch(start) {
        const queue = [start];
        const result = [];
        const visited = {};
        visited[start] = true;
        const adjacencyList = this.adjacencyList;
        
        while(queue.length !== 0) {
            const currVertex = queue.shift();
            result.push(currVertex);
            adjacencyList[currVertex].forEach(neighbor => {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.push(neighbor);
                }
            });
        }
        return result;
    }
}


const input = require('fs').readFileSync('/dev/stdin').toString().split('\n').slice(0, -1)
const parsed = input.map(el => el.split(" ").map(target => Number(target)));

const [N, M, V] = parsed.shift();
const edge = parsed;

// 그래프 생성
const graph = new Graph();
// 그래프 정점 추가
for (let i = 1; i <= N; i++) {
    graph.addVertex(i);
}
// 그래프 간선 넣기
for (let i = 0; i < M; i++) {
    const [v1, v2] = edge[i];
    graph.addEdge(v1,v2);
}

// 각 정점에 연결된 정점들 오름차순 정렬
Object.values(graph.adjacencyList).map(el => el.sort((a,b) => a-b))

// DFS, BFS 결과
const answer = [];
answer.push(graph.depthFirstSearch(V).join(" "));
answer.push(graph.breadthFirstSearch(V).join(" "));
console.log(answer)

console.log(answer.join("\n"));

fgstudy 2년 전 0

결국 클래스 말고 함수로 풀어서 해결되었습니다! 데이터 구조가 Map이라 Object.values로 정렬했었어야만 했고, 잘 된줄 알았었는데 반례가 있나보네요..
도저히 반례를 못찾겠어서 그냥 함수로 풀었습니다! 혹시 위의 코드에서 문제가 되는 부분을 찾으신다면 알려주신다면 감사합니다!

js로 코테할땐 그냥 배열로 데이터 구조만드는게 맘편하네요.. 클래스 no.....

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[node.js] 선배님들 반례 부탁드립니다 ㅠㅠㅠ...

fgstudy 2년 전 0

fgstudy 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말