그래프와 순회. [24479], [24480]

[1. 문제 설명]

무방향 그래프가 주어졌을 때

시작 정점에서 dfs 시, 각 정점에 방문 순서를 출력하도록 한다.

(인접 정점이 여러개인 경우 오름차순으로 정점을 방문하도록 한다.)

방문 할 수 없는 경우 0을 출력하도록 한다.

 

[2. 풀이 접근]

실수했던 사항

1. 메모리 사용량
   => 문제에서 주어지는 정점의 개수는 최대 10만개
   => 인접행렬로는 그래프 구현이 불가 (메모리 사용량 때문에)
   => 인접리스트로 구현 시, golang 에서 slice 를 사용하였는데, cap 를 10만으로 설정하여, 메모리 초과가 발생
   => len: 0, cap: 0 으로 각 정점에 주어진 인접리스트를 초기화함
   
   
2. 그래프 구현
   => 주어지는 그래프는 무방향 그래프
   => 처음에 edge 를 단방향으로만 여겨서 오답처리 되었음
   => edge 를 처리할 때, 양방향으로 처리해야 함
   
   
3. Stack 으로 구현 시 주의 사항
   => 재귀와 달리 stack 으로 구현 시, stack 에 아직 방문하지 않은 정점을 푸쉬하고,
   => 이후 실제 방문 시 방문 순서를 업데이트 하는데,
   => 경우에 따라서는 이미 stack에 푸쉬 된 정점을 다시 푸쉬 할 수 가 있음
   => 그림1과 같은 그래프인 경우, 정점 4 가 두번 stack 에 푸쉬 됨 
   => 따라서 이미 방문한 정점이 stack 에서 pop 된 경우 이에 대한 처리가 필요함

그림 1

 

 

[3. 코드 - 24479, 재귀로 구현]

 

 

 

[4. 코드 - 24480, 스택 으로 구현]