[CodeTree] 상하좌우 반전시키기
문제
상하좌우 반전시키기 설명 | 코드트리
상하좌우 반전시키기의 요구사항을 정확히 분석하고, 적절한 알고리즘을 고안해 두 번째 단계 중급 문제를 해결해보세요.
www.codetree.ai
풀이
그리디 알고리즘을 활용하는 문제입니다.
저는 이 문제의 풀이를 끝내 생각하지 못 했고 그리디 알고리즘에 대한 개념을 다지기 위해 해설을 바탕으로 사고 방식을 정리해보려고 합니다.
먼저 하나의 칸을 기준으로 이 칸의 값을 바꾸기 위한 경우의 수를 생각해봅시다.
아래 격자 중 파란색 칸의 값을 바꾸기 위해서는 어떠한 칸을 눌러야 할까요?
누른 칸 + 동서남북 칸을 모두 바꾸기 때문에 아래의 초록색에 해당하는 칸을 누르면 됩니다.
저는 여기서부터 굉장히 막막했습니다.
5가지 경우를 모두 고려하면서 그리디하게 접근해서 이 문제를 해결할 방법이 도무지 떠오르지 않았습니다.
그런데 5가지 경우를 모두 고려하면서 그리디하게 접근할 필요가 없었습니다.
바로 이 문제의 핵심은 첫 번째 행에 존재하는 칸들은 누를 수 없다는 점 때문입니다.
그리고 격자의 모든 칸들은 1이 되어야 하고 당연히 첫 번째 행에 존재하는 모든 칸들 또한 1이 되어야 합니다.
첫 번째 행의 값을 바꾸려면 그 다음 행의 동일한 열에 해당하는 칸을 누르는 방법 밖에는 없습니다.
즉, 경우의 수가 5가지에서 1가지로 줄어들게 됩니다.
이렇게 되면 쉽게 그리디를 적용할 수 있습니다.
다음과 같은 경우를 생각해봅시다.
첫 번째 행의 값들을 모두 1로 만들기 위해서는 빨간색 칸은 절대 누르면 안 되고 파란색은 칸은 반드시 눌러야 합니다.
그렇게 누르고 나면 두 번째 행의 값은 확정이 되고 두 번째 행의 칸들은 두 번 다시 누를 수 없습니다.
그렇다면 두 번째 행의 값들도 모두 1로 바꾸기 위해서 세 번째 행의 칸을 눌러야 합니다.
이런 식으로 점진적으로 나아가면 문제를 해결할 수 있고 마지막 행의 값들 중 0이 존재한다면 해당 격자는 모두 1로 만들 수 없게 됩니다.
처음에는 모든 경우의 수를 생각했기 때문에 굉장히 막연했지만 점진적으로 나아가면서 그리디 방식으로 문제를 해결할 수 있었습니다.
만약 첫 번째 행의 칸들을 누를 수 있다면?
문제를 풀고 나서 문득 궁금한 점이 생겼습니다.
만약 첫 번째 행의 칸들을 누를 수 있다면 그리디 방식을 적용하지 못 하는 걸까요?
관련된 질문을 올렸더니 brute force + greedy 방식으로 문제를 해결할 수 있다고 합니다.
우선 이 문제에 그리디 방식을 적용할 수 있었던 이유는 뭘까요?
첫 번째 행의 모든 칸들의 값들이 고정되어 있었기 때문입니다.
그렇다면 첫 번째 행의 칸들을 선택할 수 있다면 첫 번째 행의 모든 칸들의 값이 고정되어 있지 않게 됩니다.
이 때, brute force 방식을 적용하여 첫 번째 행의 모든 칸들의 값을 고정하면 greedy를 적용할 수 있게 됩니다.
즉, 첫 번째 행의 칸들을 선택하는 모든 경우의 수를 고려하면 됩니다.
각 칸들은 선택하고 선택하지 않는 경우 총 2가지 경우가 존재하기 때문에 경우의 수는 2의 n제곱이 됩니다.
이 2의 n제곱 경우의 수를 모두 고려하여 똑같이 greedy를 적용하면 문제를 해결할 수 있게 됩니다.
마무리
아직 그리디에 대한 개념이 많이 부족하다는 것을 느낄 수 있었던 문제였습니다.
항상 점진적으로 접근하는 사고 방식을 지녀야 할 것 같습니다.