shyram   5년 전

이전 문제에서 스택과 큐를 구현해서 이번에도 필요한 부분만 구현하여 쓰게 되었습니다.

DFS같은 문제를 처음 접합니다.

탐색을 하기 위해서 스택과 큐를 구현하고 DFS와 BFS 함수를 만들었습니다.

main에서 각 정점들의 간선을 2차원 배열을 통해서 만들었습니다.

DFS함수에서는 먼저 탐색을 했는지 여부를 따지기 위해 boolean형 배열을 선언했습니다. 정점의 개수가 N이고 모든 정점이 서로 연결되어 있다는 가정 하에 스택에 들어갈 수 있는 숫자의 최대 개수는 N(N-1)/2 - N+2 개로 계산했습니다. 넉넉하게 N(N-2)/2 크기의 스택 선언했습니다.

큐도 마찬가지로 같은 갯수로 선언했습니다.

처음에 만든 소스코드는 큐와 스택의 크기에 문제가 있다고 판단했습니다. 제 나름대로 계산한 결과 넉넉한 크기를 선언하게 되었습니다. 그 결과 100퍼센트까지 가다가 런타임 오류가 발생했습니다.

for문에 문제가 있는 것인지 스택이나 큐의 크기에 문제가 있는 것인지 잘 모르겠네요.

어디에서 런타임 오류가 발생하는 것 일까요??

그리고 런타임 오류는 주로 배열의 크기와 값을 잘못 지정하거나 값이 없어서 발생하는 것으로 알고 있습니다. 런타임 오류가 발생하는 다른 주요한 원인에는 뭐가 더 있을까요??

djm03178   5년 전

그 크기로는 충분하지 않습니다.

사실 효율적으로 코드를 짠다면 큐나 스택의 크기는 N이어도 됩니다. 큐에 스택에 삽입할 때, 같이 방문 체크를 해서 넣으면 중복해서 정점이 들어갈 일이 없기 때문입니다.

shyram   5년 전

감사합니다! 잘못 계산한 것 같습니다..ㅠㅠ

중복 체크 추가해보도록 하겠습니다!

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