처음부터 문제를 잘못 접근했다면 (feat. 그래프 알고리즘)

1. 방의 개수 찾기 문제

원점 (0, 0)에서 시작해서 위와 같이 숫자가 적힌 방향으로 이동하며 선을 긋는다. 그림을 그릴 때, 사방이 막히면 방 하나로 센다. 이동하는 방향이 담긴 배열이 매개변수로 주어질 때, 방의 개수를 반환하도록 solution 함수를 작성하세요.

프로그래머스

 

2. 먼저 해답에 대해서..

이 문제의 해답에 대한 큰 아이디어는 다음과 같다.

각 점을 그래프의 노드라고 하고, 연결하는 선을 간선이라고 하면 이 문제의 자료구조는 그래프가 된다. 하나의 방은 (0,0)에서 시작해 이미 방문했던 노드로 다시 돌아오는 경우 방이 하나 완성된다고 볼 수 있다. 이때 일어날 수 있는 모든 경우의 수를 꼼꼼하게 생각해보면,

1. 방 하나를 카운트하기 위해서는 방문한 노드를 재방문할 때, 반드시 새로운 간선(edge)을 통해 방문해야 한다.
2. 대각선 이동이 교차되는 경우, 방은 한 번의 이동에 2개가 생긴다.

 

3. 피드백

나는 이 문제를 항상 그래왔던 것처럼 아주 큰 추상적인 레벨에서 시작해 거꾸로 생각해나갔다. 일단 문제를 해결할 수 있는 자료구조가 그래프라는 것은 직관적으로 와 닿았다. 그래서 첫 번째 단계로 연결 정보에 관한 배열을 처리해 그래프로 만들었다. 두 번째 단계로서 방의 개수를 찾아 count를 올리면 된다고 생각했다.

그러나 그래프를 그리고 노드를 연결하는 것과, 방의 개수를 찾는 단계를 분리해버림으로써 완전히 진퇴양난에 빠졌다. 각 노드 당 이와 연결된 방의 개수를 찾으려고 했으나 로직이 쉽게 떠오르지 않았다.

한 노드를 시작점으로 생각해 연결된 노드를 방문해가며 방문 여부를 체크하는 식으로 생각했다. 혹은 순환하는 모든 경로를 구해, 각 경로에 방문한 노드를 집합에 넣고, 집합들의 각 원소를 비교해가며 서로 다른 방인지 체크하는 식이면 어떨까 생각도 했다. 뭘 하든 복잡했던 것 같다.

책에 나온 해답은 아예 그래프를 그리는 과정에서 동시에 방의 개수를 counting 하는 것이었다. 괜히 처음부터 그래프의 노드와 간선을 연결하고 난 다음, 도형 찾기 문제에 돌입한 것이 실수였던 것 같다. 

그러니까, 내가 처음부터 그래프 자료구조를 모두 만들고 난 다음에서야 비로소 알고리즘을 구상한 반면, 위 문제의 해답은 아예 그릴 때부터 미리 알고리즘 문제를 푸는 것이었다.

내가 하는 식으로도 문제 풀이가 불가능할 것 같진 않다고 생각한다. 하지만 로직이 굉장히 복잡할 것이고, 때문에 작성 과정에서 실수를 많이 할 것 같다. 

하지만 아예 첫 단추를 잘못 잡아버린 것을 어떻게 깨닫고 잘못을 수정할 수 있을까? 솔직히 방법이 떠오르지 않는다.

오늘 이 문제를 풀면서 깨달은 것이 하나 있다. 추상적인 레벨에서의 상위 모듈의 설계가 잘못되면 하위 모듈이나 컴포넌트가 어떻게 문제를 풀든 전체적인 소프트웨어나 함수의 로직이 굉장히 복잡해질 수 있겠구나 싶다.