[백준 알고리즘][완전탐색] 3085번 사탕 게임

문제 정의

4종류의 사탕으로 이루어진 n*n에서 임의의 인접한 두 칸을 골라서 사탕을 교환한 후, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분을 고른다. 상근이가 먹을 수 있는 사탕의 최대 개수를 구해야 한다.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/3085)

문제 풀이

인접한 두 칸을 골랐을 때, 가장 긴 연속부분이 될 수 있도록 만들어야 한다. 긴 연속부분을 찾을 때는 하나의 알파벳에 대해서 DFS를 하면 될 것 같은데 임의의 두 칸을 어떻게 바꿔야 할지 고민된다. 굳이 바꿀필요 없이 모든 좌표에 대해서 DFS를 하고, 만약 막혀서 더이상 못한다면 그 자리와 인접한 칸에 사탕이 이어지는지를 판단해서 가능하면 그 칸을 바꾼다 생각하고 시도해본다. DFS 한번할 때 한칸을 바꿀 수 있도록 하면 한칸을 바꾸고 이어서 탐색을 한다. 다음 DFS도 해야하므로 실제로 칸의 값을 바꾸진 않고 해야한다.

생각한 위의 방법대로 코드를 작성했는데 틀렸습니다를 받았다. 고려했던 부분을 정리해봐야겠다.

1. 모든 칸에 대해서 아래로 혹은 오른쪽으로 얼마나 연속부분을 가지고 있는지를 DFS해서 계산한다. 가장 큰 연속부분의 값으로 업데이트해서 하나의 변수에 저장한다.

2. 두 사탕의 자리를 바꿀 한번의 기회가 있으므로, 만약 연속부분의 길이를 구하다가 막힌다면 아래쪽을 보고있을경우는 그 자리의 양옆과 그 아래칸을 봐야한다. 그리고 오른쪽으로 가고 있을 경우는 그 자리의 위아래와 그 옆옆칸을 봐야한다. 

여기서 정리하면서 어느부분을 틀리게 작성했는지 찾았다. xDFS, yDFS로 두가지의 함수를 만들었는데 모르고 오른쪽으로 갈 때도 그 자리의 양 옆과 아래칸을 보도록 함수를 복사해버렸다. -> 다시 확인해봤는데 x, y에 대해서 두 변수에 더하는 수를 바꿔줘서 문제가 없었다.

계속해서 예시를 생각하다가 문제점을 발견했다. 작성한 코드의 문제점은 아래쪽으로 쭉 갈경우, 오른쪽으로 쭉 갈경우 DFS로 수행이 되는데 만약 막힐 경우 가장 첫 경우에만 사탕을 교환한다. 다른 리뷰들을 보면 전부 swap하여서 문제를 해결했길래 왜 그렇게 풀었는지 다른 방법이 있을거라 생각했는데, 한번밖에 사탕을 교환할 수 없으니까 모든 경우에 대해서 교환을 해보는 완전 탐색으로 구현을 해야한다. 완전 탐색을 하여고 n이 50이하이기 때문에 최대 50*49*2번밖에 수행하지 않는다.