[백준] 파이프 옮기기 1

유승선 ·2022년 6월 16일
0

백준

목록 보기
22/64



시뮬레이션에 꽤 강하고 BFS 같은 탐색류의 문제에 나는 강력하다고 믿고있다. 그러나 최근에 좀 나를 괴롭히는 유형의 문제를 자주 풀고있는데 예를들면은 모든 로직과 코드가 맞았지만 미세먼지때 문제처럼 회전을 어느 특정한곳에서 안시작해서 틀렸다든지 등. 정말로 많은 시간낭비를 할때도 있어서 속상하다. 그리고 이번 문제도 사실 나의 속을 태웠던 문제이기도 하다.

이 문제는 삼성기출문제에 등장하는 문제로서 기본적으로 탐색과 시뮬레이션 위주의 능력을 요구하고 있다. 여기서 중요시 해야할점은 matrix 는 N * N 의 크기이고 파이프는 가로, 세로, 대각선이 있다. 그리고 파이프는 놓인 위치에 따라서 움직일수 있는 각도가 다 다른데 가로는 가로 와 대각선으로 움직이고, 세로는 세로와 대각선으로 움직이고, 대각선은 모든 방향을 움직일수있다 (가로, 세로, 대각선). 그리고 이 모든 경우의 수에서 가장 마지막인 Matrix[N-1][N-1] 에 도달할수있는 횟수를 출력하면 되는 문제이다.

먼저 이 문제를 보고 고민이 들었던거는 visited 를 써야할까 말아야할까 였었다. 그런데 문제를 그림을 그리면서 자세히 보다보니 애초에 이것은 도형에 따라서 움직이고 방문하는 포인트가 다르기에 visited 를 따로 사용할 필요가 없었다. 그러나 일반류의 상하좌우 를 요구하는 bfs탐색같은경우에는 visited 탐색이 꼭 필요하다고 생각한다. 이제 여기서 주의 해야할점은 각각 도형의 모양마다 움직일수 있는 위치가 다르다는 것이다. 그리고 대각선에 경우에는 무려 인접한 세칸마저 확인해야하는 트릭이 있다. 그러면은 우리가 흔하게 사용하는 dir 벡터를 이용해 방향을 정할수는 있겠지만 나 같은 경우 그냥 무지성으로 다 때려박았었다.

이것을 쓰는 나도 정말 어질어질 하다고 느꼈었던 코드들이었고 저것을 풀이하자면은 크게 어려운것은 없었다. 해당 좌표가 주어지면은 가로 세로 대각선 모두 구한다음에 type (파이프의 모양) 을 기준으로 컨디션을 확인해준 다음에 q에 넣었고 성공을 했다. 그러나 여기서 내가 가장 억까라고 생각했던 부분은. 모든 로직을 가지고 있음에도 "시간초과" 가 나왔던것이다. 내 C++ 로직에서는 틀린게 없었는데 너무 답답해서 다른사람의 답 또한 참고했지만 전부 나랑 똑같은 생각에 똑같은 풀이 방식이었다.

이거때문에 계속 고민하고 여러번의 전투실험을 한 결과, 주석에도 적어 두었지만 q를 만들때 vector 를 컨테이너로 넣은게 큰 화가 됐었다. 나는 한번도 컨테이너에 벡터를 넣는게 어떤 결과를 만드는지 전혀 몰랐는데 생각보다 시간이 많이 들어가는 작업이었나보다. 이것을 보안하기 위해 만든 해결책은 딱 하나다. Struct 로 대처했던것. 정말로 똑같은 로직에 똑같은 풀이지만 그저 vector 로 구성된 queue 를 제거하고 struct 로 구성된 queue 를 만들다 보니 놀랍게도 계속 시간초과 됐던 코드가 통과됐다.


개인적으로 훨씬 깔끔하다고 생각했던 코드..Struct 와 Vector 로 구성된 queue 하나의 차이때문에 이렇게 오랜 시간이 걸리다니 믿기지가 않았다. 다음부터는 queue 에 여러가지 요소가 들어가는거면 Struct 를 적극 사용해봐야겠다.

배운점:
1. Struct 의 활용
2. 당황하지 않기

profile
성장하는 사람

0개의 댓글