kimjh9434   2년 전

음냐... 지금까지 그냥그냥 막혀도 질문 게시판을 읽어나가면서 어떻게든 풀어나갔는데, 

이번에는 어떻게 접근해야할지 몰라서 처음으로 질문을 남겨봅니다.

일단, https://www.acmicpc.net/board/  에서 언급하고 있는 예제는 모두 통과했고, 

그 밖의 게시판의 질문들에서 예시로 드는 것들도 모두 통과했다고 생각합니다.

[다른 질문들의 문제점으로 ' 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문' 도 만족한다고 생각합니다]

[참고로 작업환경은 이클립스입니다]

기본적으로 그래프 문제라고 생각해서, 

좀 복잡하게 생각한 걸수도 있지만 간단하게 Graph, Point 클래스를 만들었고,

DFS용인 PointArrayStack 클래스와 BFS용인 PointArrayQueue 클래스도 만들어서 이용해보았습니다.

[이전 단계 문제에서 이미 스택, 큐 클래스를 만들어놓은게 있어서, 기본 자료형만 바꿨습니다]


기본적인 단계로는,

1. N, M, V를 입력받고,

2. N개의 점점으로 이루어진 그래프를 만들고,

3. 그래프의 인접행렬을 오름차순으로 정렬한 뒤에,

4. DFS 알고리즘 수행,

5. BFS 알고리즘 수행으로 이루어집니다.

확실히 코드 자체가 비효율적일지도 모르겠지만, 

일단 맨 처음에 생각했던 방향대로 밀고 나가다보니 저런 코드가 탄생했습니다.

그리고 일단 전체 뼈대를 세운 뒤에, 각종 예제들을 테스트하면서 발견하게 된 문제들을 해결하다보니

코드가 좀 더 지저분해진 감이 있습니다만, 일단 제가 아는 선 내에서는 문제를 해결했다고 생각하지만,

실질적으로 문제를 제출하면 20%좀 뜨는 순간 바로 틀렸다고 나와버립니다.

어디가 문제인지 안다면 해결을 시도할 수도 있을텐데, 도저히 감이 안와서 이렇게 질문을 올려봅니다.

CF. 추가적으로 시도해본 예제

15 14 15 

1 2 

1 3 

2 4 

2 5 

3 6 

3 7 

4 8 

4 9 

5 10 

5 11 

6 12 

6 13 

7 14 

7 15

입력시 =>

15 7 3 1 2 4 8 9 5 10 11 6 12 13 14 

15 7 3 14 1 6 2 12 13 4 5 8 9 10 11

djm03178   2년 전

코드가 너무 길어서 분석해드리긴 어렵고, 대신에 반례를 찾아 드렸습니다.

웬만큼 작은 케이스로는 거의 틀린 답이 안 나오네요.

kimjh9434   2년 전

오오오오!!!

사실상 반례를 못찾은 상황에서 어디가 문제인지 몰라서 방치하고 있었는데, 정말로 문제가 있더군요. [역시 컴퓨터는 잘못이 없는...] 

일단 반례상으로도, DFS는 잘 돌아갔는데, BFS의 맨 마지막 2개의 순서가 잘못되었던 것으로 보여서, 

예시 중 하나를 일일히 그려서 손 디버깅을 하던 와중에, 문제점을 찾아냈습니다.

정점이 이미 큐에 들어가 있는데, 다른 정점입장에서는 아직 방문되어있지 않나고 나와있어서 또 넣는 문제점이 보였고

아마 그거 때문에 문제가 발생하지 않았나 추측됩니다. [반복해서 넣다보니 큐의 크기인 N을 초과하는 입력이 있을 수도 있었고, 그러다보니 정확한 타이밍에 큐 삽입이 되지 않았다던지 등의 문제가 발생해서 순서가 뒤밖이지 않았나 생각됩니다. 완전히 다 전개하지는 않아서, 완전 정확한 원인까지는 잘 모르겠내요]

[사실 따지고 보면, 이 문제 자체는 전에도 어느정도 인식하고 있긴 했는데, 적어도 주어졌던 예제상으로는 잘만 돌아갔기 때문에, 큰 문제라고 생각하지 않았던 것 같기도 합니다]

DFS는 그대로 냅두었고, BFS부분만 수정하였는데,

DFS인 스택과는 다르게, BFS인 큐는 그냥 넣는 순서 그대로 출력하기만 하면 되는 거기 때문에,

기존의 일단 큐에 넣고 뺀 이후에 방문했다고 표시하고 출력하는 방식에서

 그냥 큐에 넣기 전에 미리 방문했다고 표시하고 출력도 해버린 이후에 큐에 넣는 방식으로, 

큐에 중복 삽입 방지를 구현하면서 해결했는데, 제출해보니 정답이라고 나왔습니다!

감사합니다!!!

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