백준 1260번 DFS와 BFS 풀이/코드 (파이썬) 자꾸 오류가 나는 경우 간단한 해결 방법

일단 코드만 궁금한 분은, 언제나 처럼 깃허브링크

GitHub - Rhyankwon/algorithms

 

정말 간단한.. 기본중의 기본탐색문제이다. 이거 못풀면 아무- 그래프 문제도 못 푼다고 보면 된다..라고 생각했는데 날 거의 3시간 가량 괴롭혔다. 하지만 여전히, 엄청 엄청 기초문제라는 사실은 변하지 않는다. 우선 어떻게 푸는지 설명 대강 하고, 마지막에 왜 내가 세시간 날려먹었나 한을.. 풀도록 하겠-다.

 

내가 푼 논리 (그냥 bfs dfs라 사실 논리랄것도없지만)

 

0. 미리 딕셔너리나 리스트에 각 노드마다 어떤 노드와 연결돼있는지 저장한다.

 

- dfs의 경우 -

1. 시작노드에서 재귀를 시작하고, for문 내에 dfs를 다시 호출한다.

2. 매번 새로 호출할 때마다 방문리스트에 해당 노드를 추가하고, 이미 방문한 노드는 다시 방문하지 않는다.

3. 방문 노드 수가 N이 되면 재귀함수 종료

 

- bfs의 경우 -

1. 시작 노드를 스택에 넣고 while문을 선언한다.

2. 스택에서 꺼낸 노드를 방문 리스트에 추가하고 해당 노드와 인접한 노드 중 아직 방문하지 않은 노드들을 모두 스택에 넣는다.

3. 방문 노드 수가 N이 되면 while문을 종료한다.

 

어떻게 구현하느냐 약간씩 차이가 있겠지만 기본적으로 dfs와 bfs는 각각 재귀, 스택을 활용하면 된다.

 

 

 

---------------------------잡담----------------------------------------------

 

 

그리고 가장 중요한, 내가 약 10분만에 문제를 풀어놓고 두시간 세시간동안 헤맨..이유..!!

 

아니 자꾸 11프로에서 답이..안넘어가는겨 ㅜㅜ 근데 가장 충격적이었던건 메모리초과/시간초과가 아니라 '틀렸습니다'...

 

그래프문제는 코드의 기본 틀은 거의 동일하게 항상 나오기때문에 그동안 그래프문제를 위와같은 방식으로 풀어왔던 나는 거기서 멘붕이 엄청나게 왔다. 분명 맨날 풀던대로 풀었는데 갑자기 틀렸습니다 ..?????????????? 시간초과 메모리초과도 아니고..?

 

뭔가 이상하다는걸 느끼고 다른 사람들의 코드를 찾아봤는데 구현 방식은 조금 달라도 기본 논리는 완전 똑같음. 당연한 말이겠지만ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

그래서 아니 시x 대체 어디서 틀린건지를 알수가 없어서 구현하는데에 다른 부분을 하나씩 하나씩 따라해보는..두시간을 보냈다.

근데.. 갑자기 내 눈에 띈.. 출력..방식...

 

사실 출력방식은 워낙 다양하게 구현을 할 수가 있어서 그부분을 신경도 안썼는데, 그동안 맞아온 내 코드가 갑자기 오늘 안된다고? 이건 말이 너무 안되는거같아서 출력 부분을..바꿔봤다.

 

그랬더니 갑자기 됨 ㅋ 하하 내 두시간 어디로갓누ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ진짜 죽고싶었다. 평소에 잘 풀던게 갑자기 안되니까 갑자기 엄청 우울해져서 또 나 뭐해먹고살지 이런 생각까지 했는데 알고보니 출ㅋ력ㅋ문제.

 

지금 보이는건 빙산의 일각. 엄청나게 많은 트라이를 했다,,

아무튼 왜 오류가 나는지를 알게되고 나서, 사이사이에 코드 좀 수정한거 말고 맨~처음에 내가 제출했던 코드에서 출력부분만 바꿔서 재제출했더니.. 됨..........ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

내가 처음에 했던 방식은, 리스트 출력 두줄. ->이렇게 하면 틀립니다 여러분.

이걸 for문을 써서 각각 요소, 한칸 띄기, 요소 ..이걸 반복해서 출력시켜야 11퍼센트에서 답이 맞게 넘어갑니다.

 

사실 윗쪽 방식으로 해도 답은 똑같이나옴... 그동안 이렇게 해서 맞았는데 왜 갑자기? 싶지만... 하하 내 두시간물어내~~~

 

아무튼 내가 처음 했던 방식이 맞아서 그래도..위안이 다소 됐다. 그리고 다른 사람들 코드를 봤을때 거의 무서울정도로.. 똑같이 코드를 짜놨는데 나랑 구현방식은 조금 다르지만 나도 그런식으로 코드를 짜는 쪽으로 조금 나중엔 바꿔봐야겠다. 미리 방문/미방문을 체크하는 리스트를 선언해두면 방문했는지를 확인할때 O(1)시간복잡도로 할 수 있으니까..