좋은 문제 추천 리스트를 보던 와중에 괜찮아 보여서 골라봤는데 삼성 기출문제 중 하나라고 한다. 문제는 N * N 으로 이루어진 벡터에서 해당 시나리오에 따라 인구이동이 가능한데 이 과정을 더 이상 안해도 될때까지 루프를 돌린 후에 시나리오가 끝나는 날을 출력하면 되는 문제이다.
왜인지 모르겠지만 정말 쓸데없는곳에 시간을 많이 날렸는데 input 을 넣는 과정에서 왜 시간을 썼는지 모르겠다. 하여튼, 언뜻보면은 쉬운 문제 같아 보여도 이 문제는 사실 두번을 생각해야 하는 문제고 그냥 무지성으로 문제를 잘 읽지 않고 풀었다가는 어딘지도 모르는곳에서 이게 왜 틀렸지? 하는 순간이 왔다.
가장 먼저 정사각형 모양에 Matrix안에 있는 숫자칸 중에서 인접해 있는 칸을 본 후에 시나리오대로 L 이상 R 이하인지를 확인 해줬어야했다. 나는 이 과정에서 지난 백준 문제를 풀면서 느껴본 Visited Matrix 를 따로 만들어서 사용해주었고 좀 더 수월하게 풀수있는 기반을 만들어 놨다.
시나리오에 필수 조건에서는 각 나라와 인접한 (상하좌우) 나라에 인구가 L 이상 R 이하여야 한다 했고 나는 이 조건을 만족하면 Visited 벡터에 True 를 입력해주었다. 그리고 Matrix 탐색이 끝난다면 Visited 벡터를 탐색해주어서 1이 나온 구간을 봐주었고, 그 숫자를 모두 더하고 필요한 인구수를 계산해주었다. 물론 그 다음에는 Matrix를 새로 업데이트 시켜주었고 Visited는 매번 룹 마다 초기화 시켜주었다.
만약 Visited 구간에서 True 가 한번도 보이지 않을시에는 모든 시나리오 조건을 통과했다는 뜻으로 룹을 깨주었고 answer 을 출력해주었다.
bfs 와 bfs_reset 이 있는부분이 많이 의문 스러울것인데 첫번째 bfs는 조건이 맞는지를 확인하는 탐색 부분이었다.
일반적으로 쓰이는 queue 구조를 하나도 안쓰고 그저 인접 나라들만 보면서 시나리오에 맞는 조건이 있다면 visited 벡터 좌표에 True 를 입력해주었다.
이 문제에 핵심이라고 볼수있는 bfs_reset 이라는 부분인데. 난 처음 코드를 썼을때 틀렸다. 왜냐면은 visited 벡터를 기반으로 한번 더 BFS를 해줬어야 했는데 내가 문제를 잘 안읽었던 탓인지 이해를 못했던 탓인지 이 부분이 잘 안됐어서 많이 애 먹었다 (수많은 cout 과 에러 찾기..) 하여튼, 이 BFS_RESET 함수가 중요한 이유는 total 과 cnt 를 구하는것 뿐만 아니라 Matrix를 새로 업데이트 해야할 인구수를 업데이트 해주기 위한 save_points 가 필요했기때문이다. BFS를 하는 과정에서 자연스럽게 이 전에 업데이트했던 visited 를 리셋해주고 matrix 또한 필요한 값을 넣어주었다.
이 과정을 while 룹을 통해 계속 하다보면은 언젠가는 필요없는 구간이 나왔기때문에 꽤 흥미로웠고 두번을 생각하게 만든 문제라고 생각한다.
배운점:
1. 문제 잘 읽기
2. BFS 활용
