[코딩테스트, 더 이상 미룰 수 없다] BOJ 14502 연구소 - 구현을 감 잡아보zㅏ

 

이 문제는 단순히 정답을 맞히는 것보다, 구현 문제를 어떤 식으로 바라봐야 하는지 다시 생각하게 해 준 문제였다.

구현, 조합, 시뮬레이션, 탐색이 함께 섞여 있는 문제여서 더 좋았고, 동시에 더 배울 점이 많았다.

왜 좋은 문제라고 느꼈는가

이 문제의 좋은 점은 여러 개념이 따로 노는 것이 아니라, 문제 안에서 자연스럽게 연결된다는 점이다.

벽을 3개 세워야 하니 빈 칸 중 3개를 고르는 조합이 필요하고,
벽을 세운 뒤 바이러스가 퍼지는 과정을 표현하려면 BFS가 필요하다.
그리고 그 모든 과정을 반복해서 최대 안전영역을 구해야 하니 결국 시뮬레이션 문제의 성격도 갖는다.

 

이런 문제는 단순히 한 알고리즘을 외워서 푸는 문제보다 훨씬 좋은 연습이 된다.
실제로 코딩테스트에서는 “이건 무조건 BFS”, “이건 무조건 DP”처럼 딱 떨어지는 문제보다
이렇게 구현 안에 탐색이 들어가고, 경우의 수 안에 시뮬레이션이 들어가는 문제가 더 자주 연습해야 한다고 느낀다.

 

---

이 문제에서 진짜 중요했던 건 BFS 자체가 아니었다

처음에는 바이러스를 퍼뜨리는 BFS가 핵심이라고 생각했는데,
막상 풀면서 더 중요하다고 느낀 건 “상태를 어떻게 관리할 것인가”였다.

예를 들어 벽을 세운 뒤 바이러스를 퍼뜨리는 작업은 매 경우의 수마다 새롭게 이루어져야 한다.
그러면 원본 배열은 유지되어야 하고, 실험은 복사본 배열에서만 진행되어야 한다.

이 구분이 흐려지는 순간 바로 실수가 나온다.

실제로 구현 문제에서 자주 틀리는 이유는 알고리즘을 몰라서가 아니라
원본과 복사본을 헷갈리거나, 이번 경우의 상태와 다음 경우의 상태를 섞어버리기 때문이다.

그래서 이 문제는 “탐색을 할 줄 아느냐”보다
“한 번의 시뮬레이션 단위를 독립적으로 관리할 수 있느냐”를 묻는 문제

이런 유형의 문제로 카테고리를 묶어서 생각해야 좋겠더rrr라.

 

---

앞으로 구현 문제를 볼 때 생각해야 할 점

이 문제를 풀면서, 구현 문제가 막막하게 느껴질 때는
일단 문제를 한 번에 보지 말고 상태 변화의 단계로 끊어 봐야겠다는 생각이 들었다.

이 문제도 처음에는 복잡해 보이지만, 실제로는 다음 세 단계로 나뉜다.

 

• 벽을 세운다
• 바이러스를 퍼뜨린다
• 남은 안전 영역을 센다

 

이렇게 나누고 나면 각 단계가 해야 할 역할이 분명해진다.
구현 문제는 보통 아이디어가 어려운 게 아니라, 여러 작업이 한 덩어리로 보이기 때문에 어렵게 느껴진다.
그래서 앞으로는 문제를 보면 “무엇을 몇 단계로 나눌 수 있는가”부터 먼저 생각해야겠다고 느꼈다.

 

---

특히 조심해야 할 점

이 문제에서 가장 크게 느낀 건 구현 문제는 작은 실수가 전체 정답을 무너뜨린다는 점이다.

대표적으로 조심해야 할 것은 이런 것들이다.

첫째, 원본 배열과 실험 배열을 반드시 구분해야 한다.
이번 경우의 수에서 벽을 세우고 바이러스를 퍼뜨리는 것은 원본이 아니라 복사본에서 해야 한다.

둘째, 결과를 셀 때도 어떤 배열을 기준으로 세는지 끝까지 일관되어야 한다.
실험은 temp에서 했는데 결과 계산은 board에서 해버리면, 논리는 맞아 보여도 답은 틀리게 된다.

셋째, 2차원 배열 복사는 생각보다 자주 실수하는 부분이다.
겉만 복사하면 안 되고, 각 행까지 복사해 주어야 한다.
이 문제는 그런 기본적인 복사 개념을 점검하기에도 좋았다.

넷째, BFS나 DFS보다 오히려 입력을 어떻게 저장하고, 빈 칸과 바이러스 위치를 어떻게 따로 관리할지가 더 중요할 수 있다.
즉 탐색 함수 하나만 잘 짠다고 끝나는 문제가 아니라, 탐색에 들어가기 전 준비가 훨씬 중요하다.

 

---

이 문제를 통해 다시 느낀 점

구현 문제를 어려워하는 이유는 보통 “구현력이 부족해서”라고 생각하기 쉽다. (본인이 그렇게 참 많이 느낀다.)
그런데 실제로는 구현력이 부족한 게 아니라, 상태 변화의 흐름을 분리해서 보지 못하는 경우가 많다.

이 문제는 그걸 잘 보여준다.
문제를 보고 바로 코드를 쓰기 시작하면 헷갈리지만,
상태를 나누고, 경우의 수를 나누고, 한 번의 시뮬레이션이 어디서 시작해서 어디서 끝나는지만 정리하면 훨씬 단순해진다.

그래서 이 문제는 단순한 BFS 입문 문제라기보다는
“구현 문제를 풀 때 무엇을 먼저 정리해야 하는가”를 훈련시키는 문제라고 느꼈다.

 

 

---

앞으로 비슷한 문제를 풀 때의 기준

앞으로 이런 문제를 만나면 먼저 아래를 체크해야겠다고 생각했다.

이 문제는 한 번의 탐색으로 끝나는가, 아니면 여러 경우를 반복 실험해야 하는가.
원본 상태와 실험 상태를 분리해야 하는가.
결과를 계산하는 기준 배열이 무엇인가.
탐색 자체보다 그 전에 좌표나 후보군을 정리하는 게 더 중요한가.
문제를 단계별 시뮬레이션으로 나눌 수 있는가.

이 기준을 먼저 세우면, 구현 문제가 훨씬 덜 추상적으로 보일 것 같다.