이런 유형의 문제를 플지 몰랐는데 가장 최근에 나온 문제 목록중에 재밌어 보이길래 풀어보았다. 언뜻보면 평범한 Matrix문제같고 혹은 BFS같은 유형의 문제를 떠오를수도 있었겠지만 이 문제는 BFS형태로 풀기에는 Matrix 크기가 너무 크고 시도할려고 했으면 무조건 TLE 가 나왔을거다.
문제를 살펴보자면 n * m 격자가 있고 guards 벡터와 walls 벡터가 따로 존재한다. Guards 좌표에 있는 장소는 동 서 남 북 기준으로 Walls 좌표에 막히지 않는 이상 그 방향에 있는 모든 cell 들을 커버할수있다. 그리고 문제가 원하는건 모든 cell중에서 Guards 가 볼수없는 지역에 숫자를 리턴하면 되는 문제이다.
이 문제는 Simulation, 즉 구현문제에 더 가까웠고 이런 유형의 문제를 풀어본 경험이 있었기에 좀 더 쉽게 풀수있었다.
먼저 임의에 Matrix 를 따로 만들어주었고 Guards 와 Wall 의 좌표를 입력해주었다. 그 후에는 Matrix를 탐색하면서 가드가 보이는 구간에서 전 방향을 기준으로 만든 Dir 벡터에서 X와 Y의 좌표를 업데이트 해줬다. 여기서 중요한 점은 Guards 같은 경우 전방에 있는 모든 구간을 커버할수 있다는 점이다. 그래서 내가 잘 안쓰는 while 룹을 써줬고 Wall 에 막히거나 아니면 같은 Guard 에 막히지 않는 조건에서 Guard 가 커버한 구간을 전부 숫자 3으로 바꿔줬다. X와 Y는 특정 조건문을 만들어서 Overflow를 막아줬고 모든 좌표, 그리고 방향에 대한 경로탐색이 완료되면은 마지막에 간단한 for 룹을 이용해서 커버가 안된 구간을 카운트 해줌으로서 답을 낼수있었다.
시뮬레이션 문제에 경우, 침착하게 하는게 중요한거같다. 그리고 좌표가 헷갈린다고 하면은 적절한 cout 을 사용해서 벡터를 시각화 하는게 좋은거같다.
배운점:
1. 시뮬레이션 문제에서의 시각화.
2. 방향을 이용한 while 룹.
