백준 6987 월드컵 문제 해설(파이썬), dfs/시뮬레이션 연습 문제

해설 코드만 궁금한 분은 깃허브 링크 눌러주세요~

GitHub - Rhyankwon/algorithms

문제 설명 ㄱㄱ

문제 이해는, 거의 항상 그렇듯, 쉽다. 총 6개 팀이 리그전 느낌으로 모든 팀과 각각 승부를 겨루게 되는데, 이미 결과가 모두 나온 상태로 입력값이 주어진다. 각 6 팀의 승, 무, 패가 기록되어 총 18개의 숫자가 4줄 입력되어 매 줄마다 가능한 결과인지 불가능한 결과인지를 1, 0으로 출력하면 된다.

문제 해결 논리

모든 케이스를 해봐야한다. A팀이 B팀에 대해서 이긴/비긴/진 경우 -> A팀이 C팀에 대해서 이긴/비긴/진 경우 ... -> A팀이 F팀에 이긴/비긴/진 경우 -> B팀이 C팀에 이긴/비긴/진 경우 ... -> E팀이 F팀에 이긴/비긴/진 경우까지.

다만 A팀이 B팀에 대해서 이겼다고 판단하는 경우 A팀의 '승'수를 1 빼주고 B팀의 '패'수를 1 빼줘야한다. 따라서 A팀이 이미 '승'수가 0이거나 B팀이 이미 '패'수가 0인 경우 A팀이 B팀에 이긴 경우에 대해서는 더이상 탐색은 불가능하다. 그런 경우 '무'나 B팀이 A팀에 이긴 경우에 대해 그런 경우가 가능하다면 재탐색해야한다. 여기에서 또 불가능하다고 나온다면 이전의 경우로 되돌아가서 다른 경우에 대해 탐색한다. (DFS)

이렇게 해서 F팀까지 모두 탐색을 마쳤는데 지금 승/무/패에 남은 1이 없다면 모든 경기에 대해서 알맞게 탐색을 끝냈다는 뜻이므로 1을 리턴해준다. 모든 경우를 탐색하는 문제 풀이 특성상 사이에 '불가능'하다는 결과가 나오더라도 그에 대해서는 리턴하거나 출력해주지 않고 모든 경우가 끝나도 맞다는 결과가 안나오는 경우에만 0을 출력해주는 식으로 풀이해야한다.

개인적으로는 꽤 괜찮은 시뮬레이션, 재귀 문제라고 생각한다.

------잡설------

일단 이 문제는 한달 전쯤 나를 괴롭혔었다. 적당히 규칙 찾아서 풀어보려고 했는데 당연히 될리가 없었고 그 와중에 규칙은 점점 조잡해져서 .. 문제푸는데 이미 한시간 반정도 소요했었다. 그리고 다른 사람 풀이를 살짝 봤는데 dfs를 써서 전부 확인해보는 수 밖에 없는 듯 했다. 그 날은..이미 너무 체력을 다 써버려서 ㅋㅋㅋㅋ 적당히 어떻게 풀어야하나 확인만 하고 넘어갔었다.

그리고 오늘 한시간정도 제한을 두고 풀었는데 문제 푸는 자체는.. 괜찮았다. 다만 마지막에 global을 쓰는 부분에서 헷갈려서 10분정도 써먹다가 다른사람 풀이를 적당히 보고 ..풀어버렸다. 아니 근데 나중에 다시 보니까 결국 나랑 똑같이 풀었는데 내가 너무 막판에 귀찮아져버려서? 대충대충 하다 보니까 안된거였다... 흑 이런 습관좀 고쳐야되는데. 이러면 짜증이 확 난다 ㅡㅡ 문제 잘 풀어놓고 기초적인 부분에서 남의꺼 참고해서 혼자 못 푼 느낌 드는거. 내 잘못이지만..ㅡㅡ..

ㅋㅋㅋㅋ 그래도 짜증이 난다 ,,ㅋㅋ