글 읽기 - 1260 1번예시

broccoliindb 3년 전 0

문의1. "어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다."

=> 제가 여기에서 문제가 좀 헷갈리는데, 간선이 양방향이면 두정점사이에 간선은 하나인거 아닌가요?

문의2.

1260번 1번째 예제의 답중 dfs가 왜 1243 되는지 이해가 가지 않습니다.
4 5 1
1 2
1 3
1 4
2 4
3 4
양방향라고 하면
1 => 2,3,4
2=> 1, 4
3=> 1,4
인데 1번이 시작이니까 1번에 빠져나가면 스택에는 2, 3, 4 가 들어가고 2번 3번의 값들은 이미 스택에 있으니 안들어갑니다.
문제에서 정점이 작은거부터 방문하라고 했으면 스텍에 4, 3, 2 순서대로 들어가게 만들고 결과로 출력되는건
1, 2, 3, 4 되야하는것 아닌가요?

수많은 사람들이 통과한거보면 제가 잘못생각한게 맞겠지만 1243인 이유가 잘 이해가 안갑니다 ㅠ

아래는 제 코드인데, 마찬가지로 왜 틀린지 이해가 안갑니다. ㅠ

let input = require('fs').readFileSync('/dev/stdin')
let data = input.toString().trim().split(/\n+/).map(i => i.toString().trim().split(/\s+/).map(n => +n))
const [ N, M, start ] = data[0]
const edgeList = data.slice(1)

const linkedList = new Map()
const visited = new Map()

const setVertex = (visited, item) => {
  const [parent, child] = item
  if (!visited.has(parent)) {
    visited.set(parent, false)
  }
  if (!visited.has(child)) {
    visited.set(child, false)
  }
}

const setLinkedList = (linkedList, item) => {
  const [parent, child] = item
  if (!linkedList.has(parent)) {
    linkedList.set(parent, [child])
  } else {
    linkedList.get(parent).push(child)
  }
  if (!linkedList.has(child)) {
    linkedList.set(child, [parent])
  } else {
    linkedList.get(child).push(parent)
  }
}

const init = () => {
  // Add likedList, visited

  if (!visited.size) {
    for (let i = 0; i < M; i++) {
      setVertex(visited, edgeList[i])
    }
  }
  if (!linkedList.size) {
    for (let i = 0; i < M; i++) {
      setLinkedList(linkedList, edgeList[i])
    }
  }
}
// DFS
const dfs = (start) => {
  const result = []
  const stack = []
  stack.push(start)
  visited.set(start, true)
  while (stack.length) {
    const last = stack[stack.length - 1]
    result.push(stack.pop())
    if (linkedList.has(last) && linkedList.get(last).length) {
      for (const item of linkedList.get(last).sort((a, b) => (b - a))) {
        if (!visited.get(item)) {
          stack.push(item)
          visited.set(item, true)
        }
      }
    }
  }
  console.log(result.join(' '))
  visited.clear()
}

// BFS
const bfs = (start) => {
  const result = []
  const queue = []
  queue.push(start)
  visited.set(start, true)
  while (queue.length) {
    const first = queue[0]
    result.push(queue.shift())
    if (linkedList.get(first) && linkedList.get(first).length) {
      linkedList.get(first).sort((a, b) => a - b).forEach(item => {
        if (!visited.get(item)) {
          queue.push(item)
          visited.set(item, true)
        }
      })
    }
  }
  console.log(result.join(' '))
}

init()
dfs(start)
init()
bfs(start)

broccoliindb 3년 전 0

제가 dfs를 잘못생각한 부분이 있는거로 보입니다.

dfs는 스택에 쌓기는 하지만 하나 쌓을때마다 거기에서 깊이 계속 파고드는 것이었네요.

즉 1=>2,3,4

일때 2, 3, 4를 바로 스택에 쌓는게 아니라 2에해당하는 1,4를 보고 거기서 1은 이미 방문한거니까 4를 먼저 스택에 쌓는게 우선인거였네요~

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