BOJ 1948

임계경로 문제...
메모리초과가 3번이나 뜨고 틀렸습니다도 3번이나 떴다.

많이 어려웠다.
백준님의 강의자료에 수록된 문제가 아니라 백준님의 코드가 없어서... 아 물론 백준님께서 따로 설명해주시긴 하셔서 어느정도 방향을 잡고 코드를 짰고, 예제는 가볍게 통과해서 제출을 했는데... 틀렸습니다가 나오길래... indegree를 쓰면 안된다는 것을 깨닫고 indegree를 빼고 bfs로 했더니 메모리초과... 메모리초과에 대해 검색해보니 대부분 bfs문제에서 발생하는 것 같았다.

큐에 너무 많은 데이터가 들어가서 그런건가... 그래서 다시 indegree를 쓸까 생각해보았는데, indegree를 쓸 경우 .. 그러니깐 indegree가 0인 경우만 큐에 넣을 경우에는.. 만약 1에서 시작하는데 1에서 시작해서 갈 수 없는 곳이 있다면 그리고 그 곳에서 최종 목적지나 그 전을 향하고 있다면, 가리키고 있다면 최종 목적지까지는 도달할 수 없게된다...
물론 이게 문제 조건에서 이런 경우를 배제하고 있다면 괜찮겠지만 내가 보기엔 아닌 것 같았다.

그런데 내가 메모리초과에 대해 생각하다가 싸이클이 원인이 아닌가 해서 싸이클에대해 엄청 고민했는데... 생각이 안나서 문제를 다시 읽어보니 싸이클이 없다네...

여튼 그래서 최대값 구하는 bfs에서 최대값을 구할 때 즉 기존 최대값보다 더 큰 값이 있어서 기존 최대값을 갱신해줘야할 때마다 큐에 탐색할 노드를 넣어주는 걸로 바꿨다. 이정도로도 그냥 매번 큐에 넣어서 똑같은 곳을 계속 탐색하는 것에서 많이 줄일 수 있는 것 같다.
물론 최대값이 매번 갱신되버리면 똑같을 수 있지만....

여튼 그렇게 하니 메모리초과는 사라졌지만 여전히 틀리다고 나옴...
음 그래서 뭘까 생각하면서 다른 예제들을 만들어서 넣었더니... 지나야하는 간선의 개수를 구하는 부분에서 틀렸다는 것을 알게됨.

내 코드는 지나야하는 간선을 중복해서 세고있었다... 그래서 체크어레이를 만들어서 한번 방문한 노드는 어차피 또 방문해도 경로는 같고 카운트도 같아버리니 또 방문해서 카운트할 필요가 없기때문에 방문하지 않은 곳만 방문해서 카운트를 하는 식으로 했다.

그리고 ... 드디어 맞았습니다... 근데 다시 짜라고 하면 헷갈려서 못짤듯... 그래서 지금부터sublime text, dev c++ , vim에 각각 연습으로 짜보고 다시 제출해봐야겠다.

그리고 위에서 indegree를 활용한 경우도 한 번 제출해볼까... 여튼... 다시 연습해야겠다.

오늘 이 한문제말고는 아무것도 못했다. 열심히 해야겠다.