알고리즘 공부 10일차

 

https://www.acmicpc.net/problem/14502

14502번: 연구소

오늘은 하루종일 코딩테스트 문제를 풀었다. 어제 그래프 예제를 다 안풀었어서 그래프 예제 3문제를 다 푼 뒤에 알고리즘 유형별 기출문제 파트로 넘어갔다. 총 그리디 2문제, 구현 2문제, DFS/BFS 2문제를 풀었다. 짧은 시간내에 푼 문제도 있었지만, 오래 걸린 문제도 많아서 늦게 블로그에 올리게 되었다. 오늘은 푼 문제들 중 가장 어려웠던 DFS/BFS 문제인 '연구소' 문제를 이야기해보고 싶다.

먼저 이 문제를 처음 봤을 때 가장 이상적인 벽의 위치는 어디일까를 생각해 보았다. 하지만 생각하면 할수록 너무 많은 변수들이 존재했다. 그때 N의 값이 8로 굉장히 작은 것을 보고 '혹시 벽을 설치하는 모든 경우의 수를 생각하면 되지 않을까' 싶었다.  그래서 시간복잡도를 계산해 보았더니 대강 O(N^7)정도가 나왔지만 N이 8이니까 충분할 것 같았다. 하지만 구현이 좀 어려웠다. 먼저 2차원에서의 움직임을 생각해야 했고, 바이러스의 위치, 벽의 위치, 또 벽의 위치를 고르는 조합까지 내가 많이 연습해 보지 못한 유형의 구현이 너무 많았다. 그래서 시간을 많이 투자하게 됐던 것 같다. 

우여곡절이 정말 많았다. 변수이름을 잘못넣거나, return을 까먹었거나, index를 잘못넣거나 등 나름 꼼꼼하게 체크했다고 생각했지만 틀린부분이 자꾸 나왔다. 그래서 마지막에 백준에 채점 중이 뜨니까 정말 기뻤던 것 같다. 이렇게 오래 걸리는 문제들은 할 때는 많이 스트레스 받아도 끝내고 나면 정말 기분이 좋다. 좋은 꿈을 꿀 것 같다. 오늘은 내가 문제 풀면서 작성했던 아이디어 노트와 백준 채점 결과를 올리면서 마무리 하겠다!

백준 채점 결과

연구소 아이디어