SSAFY B형 후기

처음엔 굉장히 가벼운 마음이었음
최근들어 PS에 흥미가 좀 떨어져 있었고.. 예전처럼 많이 풀어보지도 않았기 때문에. 그리고 SDS Pro 준비할 때도 열심히 구현에 대해 공부했었는데 결국 유형의 문제를 겪었기 때문에

문제 건드릴 줄 알고 최적화 방법만 떠오를 수 있을 수준이면 풀수 있지 않나

라는 생각이었다

결론부터 말하자면
1. 이미 trash코드는 최적화에 별 의미도 없으니 처음부터 걸러야 했다
2. 최근에 풀어본 유형이어야 제대로 솔루션을 적용할 수 있다

라는 것을 많이 느끼게 해줬지

B형 문제의 첫인상

매우 흔~~하게 나오는 맵이었고 못가는 구역이 있고 갈수있는 구역이 있는데 맵에 있는 유형들이 벽/빈칸/무언가 식의 3개만 등장하는 문제였기 때문에

에러를 유의하며 하드코딩할 문제는 아니구나

라는 생각이 들었고 한번만에 합격할 수 있겠다는 생각을 했음

애초에 한 테케에 대한 실행 가능 횟수를 계산했을 때 1,250,000이었던 것 같음
맵 크기가 최대 350 X 350 = 122,500 이고, 무언가는 최대 200 이었는데 이게 되나 라는 생각을 하긴 했음
생각만 하면 뭐하냐 처음부터 적용을 했어야지
참고) 숫자는 대략적으로 기억나는 것만 썼으니 정확하진 않을 수 있음

그래서 풀이는?

1) 비트마스킹을 너무 믿질 말았어야 했는데..

일단.. 내가 굉장히 잘못 길을 틀었다라고 생각하는 부분이 있었는데
[1194] 달이 차오른다, 가자. 이 문제와 상당히 유사하다고 생각했음

저 문제도 어느 열쇠를 가진채로 문에 방문했는지를 기록해야 풀리니까 비트마스킹 방문처리로 풀었는데, 이 무언가도 열쇠와 유사한 역할을 한다고 생각해서 그대로 계산해봤음

여기서 치명적인 실수를 하는데...

열쇠 1번, 3번, 4번, 7번을 가진채로 (x,y) 좌표에 방문했다
=> 1001101(2)
라고 표시하면 됨

그러면 당연히 무언가는 최대 200이니까 2진수로 풀었을 때 200자리, 즉 2^200의 값을 필요로 함

계산해보지 않아도 절대 써서는 안될 값이지만...

어우 너무 크네;;

나는 너무 당연하게
2^8 = 256이니까 8자리 정도로 충분히 커버가 되겠네
라고 생각한거임;;

그래서 열심히 로직짜고..
음 이정도면 다 돌아가겠네 하며 자화자찬 중에 코드를 실행시켰는데
java.lang.ArrayIndexOutOfBoundsException 에러 ㅎㅎㅎㅎㅎㅎㅎ

진심 내 로직 완벽했는데 이게 왜 안됨? 하다가.. 깨달음 ㅎㅎㅎㅎㅎ

2) 짠 로직이 아까운데 방문처리만 좀 바꿔보자..

진짜 말 그대로 로직 짠게 너무 아까운거임
온갖 최적화 다 넣은 코드였고 논리적으로 문제될게 하나 없는데 이걸 비트마스킹 실수로 날린다?
근데 사실 이런 경우는 날리는 게 맞음. 생각이 그 솔루션에 꽂혀버리니까

무튼 아까웠음 너무 아까워
그래서 방문처리만 어떻게 안되나 하다가.. 비트마스킹을 배열로 그대로 옮겼음
000001000(2) => boolean vis 배열 선언하고 vis[3]=true 한 값
당연히 최단거리였으니 bfs를 썼는데 각각에 대한 방문처리니 같이 큐에 담았어야 했음..
어쩔 수 없이 좀 무겁게 담아보긴했다.

그렇게 돌려보니 아니나 다를까 모든 테케 solve ㅎㅎㅎㅎ
그치 로직이 틀릴 수가 없지..
그러고 검정사이트에 돌려보니 25개 태케중에 18개 까지 실행되고 그 이후 시간초과 뜨더라..

보통 무거운 로직이 되었으면 버려야하는게 맞음
근데 이거 백트래킹쓰면 좀 괜찮지 않을까 하는 생각이 들어서
조건들을 생각하며 막 추가했음 (if문 3개 정도 넣음)
근데 안줄더라 ㅎㅎㅎㅎ

3) 내가 생각하는 진짜 무조건 풀리는 솔루션임

그러면 뭐하냐고 40분 남기고 떠올랐는데...

일단 문제가 크게

벽 설치됨 : 고정위치
빈칸 : 특별할 거 없는 빈칸, 당연 갈 수 있고 A 설치 가능한 장소임
A : 빈칸에만 설치가능, 추가/삭제 구현해야 됨
(여기서 A는 특별한 기능이 있음. 이건 보안상의 이유로 언급하지 않을테니 알아서 응용해보시길)

출력 => A1 ~ A2 까지 최단거리

이런식으로 주어져 있었음

맵이 상당히 크기 때문에 사실 맵 안에서 놀았으면 안됨
그러면 맵에 있는건데 맵안에서 놀지 않을 수 있는 방법이 있나? 싶겠지만

여기서 벽이 추가되거나 삭제되는 경우가 없기 때문에 가능함

왜냐, 벽이 추가되거나 삭제되면 A1에서 A2까지 갈 수 있는 최단경로가 바뀔 수 있음
근데 벽이 고정이면 최단거리를 A1에서 아무리 다른 경로로 A2에 가려해도 같은 결과가 나올 수 밖에 없음
=> 중복연산임!!

그러면 이런 중복연산을 어떻게 줄이냐 => 맵을 축소시키면 됨
경로 압축처럼 이용하는 거임

위 그림은 실제 최단거리를 구할 때 bfs로 타고 들어가는 것처럼 보이겠지만 시각화를 위한 그림일 뿐, 실제론 A 추가 연산을 실행할 때 아래 그림처럼 진행해서 이미 전처리를 한다!

그 뒤 최단거리를 구하는 메소드에선 BFS를 진행하면서 가중치는 더하고 A에 도착했다면 A만의 특정 연산을 진행하는 방식으로 기존보다 더 효율적인 코드로 만들 수 있음!

회고랄까 그냥 후회?

이걸 한 20분이라도 빨리 깨달았다면 바로 제출했을 텐데
아직 아쉬운 마음이 너무 가득하다..

그렇지만 이번 B형치면서 PS에 대한 흥미가 다시 생겼고 시간제한이 있어 좀 쫄깃한(?) 마음으로 시험에 응시할 수 있었어서 꽤나 즐거운 경험이었다고 생각한다-!

다음주 1학기 마지막 B형 기회가 있는데 이번에 꼭 따고싶어서 어제 SDS Pro 합격결과를 본 잠실 아쿠아가든 카페에 어제 방문하고 왔다 ㅋㅋ
비록 늦게가서 전면에 전시된 어항 속 물고기들만 보고왔지만 괜히 두근거렸음~~

기운도 다시 받았겠다 남은 6일동안 열심히 연습해야지 🔜