백준 3085번 사탕게임 풀이/해설/코드 (파이썬) 112ms풀이 /DFS

코드만 궁금한 분은 링크

GitHub - Rhyankwon/algorithms

문제 : 숫자들이 든 격자가 주어진다. 이 때 인접한 요소 두개를 아무거나 바꿀 수 있는데, 이 때 전체 격자에서 일직선으로 인접한 요소들의 숫자가 같은 경우...의 가장 긴 길이를 구하면 된다.

일단 내 풀이는 대충 dfs를 활용한 완전탐색이다.

1. For문으로 각 요소마다, 왼쪽 위 오른쪽 아래 각 방향으로 탐색을 하는데

2. 다음 요소의 값이 현재값(시작값)과 같은 경우 계속 탐색을 한다.

3. 이 때 만약 어떤 값이 시작값과 다르고, 아직 한번도 인접요소와 값을 바꾼 적이 없는 경우 주변 값을 한번 바꾸고 만약 2를 만족할 경우 다시 탐색을 시작한다.

4. 격자의 끝에 도달하거나, 인접요소를 1회 바꾸고도 탐색 중 시작값과 값이 다른 요소가 나오는 경우 탐색을 멈추고 길이를 확인한다.

시간복잡도는 O(n2)이다.

아주아주 잘풀린다. 풀이 속도도 짧고.

다른 사람들은 혹시 더 잘 풀었나 싶어서 확인해봤는데 확실히 논리자체는 더 쉬운 풀이논리가 존재한다.

어차피 1회 바꾸는건 똑같으니까, 처음에 시작할 때부터 근접요소와 값을 바꾸고 그 때 일직선으로 가장 길게 인접요소들의 값이 똑같은 ..것의 길이를 찾는것이다. 난 왜 이런 생각을 못했지?ㅋㅋㅋㅋ하는 생각이 우선 들었다. 대충 내 풀이랑 시간복잡도도 비슷해보여서. 그런데 다른사람 코드를 가져와서 실행시켜보니 풀이 속도가 30배 가까이 났다;;

사이에 다른걸 좀 해보느라 에러가 한번..

내 풀이가 조금 운좋게 빨리나온건가 싶어서 두번 돌려봣는데 오히려 더 빨라졌다. 다른 사람들 풀이도 이 사람 풀이가 그냥 느린건가 싶어서 3명의 다른 풀이를 시행해봣다. 그리고 확실히 내 풀이가 빠르다고 느낌.

두번째 풀이의 경우 dfs안에서 전체요소에서 시작하는..각각의 경우에서 완전탐색을 해야하기때문에 dfs안에 이중for문이 들어가게되는데 아마도 그게 문제인것같다. (On4) 나도 dfs안에서1회 반복문을 사용하긴 하지만 그것도 요소가 이전값과 다른 경우에만 딱 4회 반복하는거라서 아마도 이부분에서 속도를 비교가 안되게 줄일 수 있었던게 아닌가 싶다.

논리적으로는 확실히 두번째 풀이가 더 쉬워보이는데 막상 뚜껑을 열어보면 효율면에서 그렇지도 않다는게 코딩의 매력이 아닌가 싶다.

그래도 이렇게 조금 더 깔끔하게 풀이할 수 있는 논리를 생각해낼 수 있는건 좋은 일이고 아직 내게 연습이 많이 필요한 일이다.