요즘 아침에 일찍 일어나서 문제를 푸는 삶은 시전하고 있는데 어떤 패기를 앞세워서 몸풀기로 이 문제를 골랐다. 알고보니 이 문제는 골드2 수준에 꽤 어려운 문제에 속해 있었고 솔직히 몸풀기로 시작했는데 그냥 몸학대 같았다. 문제 설명은 여느 백준 문제들이 그렇듯 좀 웃긴 시나리오 였다.
R X C 크기에 동굴 (matrix) 이 주어지고 두명의 사람, 창영과 상근이가 N만큼의 횟수만큼 막대기를 던지는데 한명은 왼쪽에서 던지고 다른 한명은 오른쪽에서 막대기를 던져서 서로 턴이 왔다 갔다 한다 (여기서부터 어질어질 했다) 그 막대기는 미네랄 ('X') 에 닿으면 사라지고 접촉이 된 해당 미네랄도 같이 터지게 된다. 그렇게 N만큼의 막대기를 던졌을때 남게되는 동굴의 모양을 출력하면 되는 문제였는데 언뜻보면은 쉬워 보일수도 있는 이 문제는 여러가지 디테일하게 고려할점이 있었다.
X는 미네랄을 나타내는 표시지만 X가 상하좌우로 인접하면은 클러스터 (cluster) 을 만들게 된다. 그리고 막대기에 미네랄이 맞아서 혹여나 클러스터를 유지하고 있는 바닥 미네랄이 파괴될경우에는 이 클러스터는 밑으로 떨어지게 된다. 밑으로 떨어지는 조건은 다른 미네랄과 맞닿았을때, 혹은 완전 바닥으로 떨어졌을때 추락이 멈추게 된다. 이 문제 전에 풀었던 뿌요뿌요, 그리고 프렌즈 4블록에서도 이렇게 밑으로 떨어지는 조건은 경험해봤다, 그런데 이 문제가 그런 문제보다 더 어려워진 이유는 클러스터가 떨어질때는 클러스터에 미네랄 하나하나가 떨어지는게 아닌, 클러스터 그 모양 그대로 떨어지게 구현을 했어야 했다.
이 그림에서 그렇듯, 4번째 ROW 에 오른쪽 미네랄을 제거할경우, 오른쪽 미네랄과 연결되있던 클러스터는 하나씩 떨어지는게 아닌 그 모양 그대로 떨어지는것이다.
코드를 구성하는데 상당히 까다로운 부분들이 많았었다. 가장 먼저, 왼쪽과 오른쪽을 기준으로 미네랄을 하나씩 제거하는건 어려운 조건이 아니였다, 하지만 여기서 중요하게 처리해야 되는 부분들은
- 클러스터 위치 찾기
- 클러스터 모양 찾기
- 클러스터가 그 모양 그대로 떨어지는 코드 구현
이거였었고 상당히 애를 먹었던걸로 기억한다. BFS 와 DFS 류는 이미 풀만큼 풀었다 생각했는데도 어려운 부분인거같다. 2번에 클러스터 모양 찾기는 BFS로 해결을 했고 아래는 내 코드다.
가장먼저 필요한 셋업들. 2D 어레이를 저렇게 만드는건 내 스타일이 아니지만 일단 급하니 저렇게 만들었다.
일단 여러가지 주석을 달긴했는데, 난 두 사람이 막대기를 던질때마다 모든 과정을 초기화 해주어야했다. 왜냐면 각 막대기로 던질때마다 Matrix 모양을 변형해주느 작업이 필요했고 이는 visited 또한 리셋해줘야했기때문이다. 간단히 얘기해서 fix_mineral() 함수는 막대기로 미네랄을 제거했을때/제거하지 못했을때를 표현하고 싶었던거고 왼쪽과 오른쪽의 차이는 i를 기준으로 골랐다.
두번째 find_cluster() 은 클러스터를 찾는 과정을 표현한거고 이때 cluster 벡터를 이용해서 클러스터가 생길시에 원소를 담아두었다. 만약에 클러스터 벡터가 비어있다면 그 말은 아무 클러스터도 발견 못했단 거기 때문에 continue.
여기서 중요한점, 땅 위에서부터 matrix를 서치해주고 bfs를 해주었다 왜냐면은 땅위에서 부터 연결된 모든 미네랄을 서치해주고 싶어서였기 때문이다. 그렇게 되면은 두번째 for 룹에서 연결되지 않은 미네랄 구역 (클러스터) 를 visited 벡터를 이용하여 찾을수 있기떄문이다
BFS 함수이다. 쪽팔린데 여기서 내가 메모리 초과가 계속 났었고 원인을 몰랐는데 알고보니 visited[nx][ny] 를 업데이트 해주는것을 깜빡했다. PQ 를 이용한 짧은 distance를 찾을때는 어떤 특정 조건에서 return 을 해줘서 메모리 이슈가 없었는데 bfs는 모든 원소를 찾는 작업이다 보니 저런게 필요했던거같다. 안그렇다면 q가 끝나는 조건이 없기때문에 휴..하나를 또 배웠다.
클러스터의 위치를 찾게되고 어떤 모양인지를 완전히 다 찾았으니 이제는 matrix를 변형 해주어야한다. 이 과정은 내가 너무 어려움을 겪었어서 다른 사람의 블로그를 참고해서 도움을 받았는데 상당히 괜찮은 방법이었고 내가 막혔던 생각을 뚫어준거같았다.
먼저 check_distance(x,y) 이 부분은 꼭 필요한 부분중 하나인데 각 cluster 에 저장되있는 좌표를 읽으면서 이 좌표 하나 하나가 떨어지게 될경우에 다른 미네랄 x에 닿거나 바닥에 떨어지기 까지 얼마나 많은 카운트가 걸리냐를 찾는 함수였다. 그런데 여기서 주의할점은 만약에 한 지점 x에서 떨어졌는데 닿은 x 좌표가 그냥 또다른 클러스터의 일부분일 경우 탐색이 불가능 하기때문에 INT_MAX를 리턴해주었다. (내가 깜빡했던 디테일)
그렇게 distance를 구하다 보면은 결국 마지막에는 최소한으로 떨어져야하는 distance 를 구할수 있게 되고 현제 가지고 있는 cluster을 sort() 해서 오름차순으로 만든 후에 역순으로 탐색하면서 좌표 x에 밑으로 떨어질수있는 distance를 더해주고 'x'와 '.' 을 교체 해주면 됐었다. 난 이부분이 정말 생각을 못했던건데 sort() 가 꼭 필요한 이유는 아무 오더없이 x좌표를 더해줄경우에는 결국 겹치는 클러스터 때문에 다른 답이 나왔을거다. 그렇기 때문에 역순으로 해주는게 가장 안전한 부분.
이 과정을 거치면은 코드가 완성이 되고. 정말 상당히 난이도가 있었던 simulation 겸 bfs였던거 같다. 앞으로는 좀 더 쉬운 문제 좀 풀어야겠다 너무 머리아프다. https://yabmoons.tistory.com/263 이분의 블로그를 참 좋아하는데 많이 참고했었다.
배운점:
- BFS 를 이용한 큐를 사용할때, 어느 특정 조건에서 리턴될수 있는 상황이 아니라면은 이동하는 좌표까지 visited 로 표시해줄 필요가 있다, 안그러면 메모리 초과 나온다.
- 어느 특정 구역을 알고싶을때는 bfs와 visited 조건을 이용하여 찾을수 있다.
- 시뮬레이션 문제는 어려운거는 어렵다.
