근황으로는 여러 자소서를 쓰고 새로운 일 또한 시작하면서 바쁜 생활을 했다. 그래도 코딩 테스트에 대한 열정과 감은 잃고 싶지 않기에 쉬는 날에는 꾸준히 문제를 계속 풀면서 기량을 유지하고 싶었다.
오늘은 백준에서 나온 Backtracking 추천 문제인 무기 공학을 풀어봤는데, 처음 문제를 읽었을때는 이게 어떻게 backtracking 이지? 하는 생각이 많이 들었다. 일단 N * M 크기의 배열을 만들게 됐는데 각 숫자마다 만들 수 있는 모양의 무기는 총 4개이다. 여기에 더불어서 만들어진 모양의 값을 더해야 하는데 각 무기마다 점수가 두배로 되는 부위가 다르다. 이런식으로 무기를 해당 모양으로 만든 후에 가장 높은값을 가진 무기의 값을 출력하면 된다.
내가 처음 생각했던 과정은, 각 index를 접근하며 DFS 방식으로 모양의 맞게 탐색을 해주고 가장 큰 값이 있다면 그 모양마다 더 해주고 최종값을 내는 형태였다. 그러나, 생각하고 접근하는 방식이 점점 복잡해져가지고 내가 노트에 적는 와중에도 뭘 적는지를 놓쳤었다. 그런 과정을 거치고 나서야 이게 왜 backtracking 인지 알게 되었고 아예 시작부터 모든 모양의 가능성을 넣어주며 visited 벡터를 사용하고 모은 무기들의 최종값을 max 값으로 계산해주면 되었다.
여기서 내가 느꼈던 어려운 점이 하나 있었는데 나는 지금까지 1차원 벡터에서만 임의에 index를 활용하며 backtracking 해주었지만 2차원 벡터를 사용하며 for 룹으로 index를 컨트롤 하기에는 하나를 자꾸 놓치는 기분이었다. 그렇기 때문에 내가 초반에 for 룹으로 접근했던 backtracking 방식은 결국에 원하는 모양을 전부 얻고 최종값을 내기에 하나씩 부품이 빠졌었다. 그래서 고민을 하던 와중에 나랑 가장 근접한 접근 방식을 가졌던 사람의 답을 보니 아예 for 룹을 안쓰고 2차원 벡터에서 i 와 j 의 값을 수동적으로 조절을 하며 답을 찾는 방법을 보았고 그대로 사용해봤다.
조금 조잡하지만, 각 모양의 가능성을 먼저 확인하기 위한 사전 작업이었다.
만약에 해당 index에서 shape에 따른 무기를 만드는게 가능하다면은 visited 로 표시를 해둠과 동시에 최종값을 전부 계산해주고 리턴해주었다.
그렇게 도출된 결과이다. 아예 for 룹을 배제하며 i와 j 인덱스를 내가 수동적으로 관리해주었고, 언제 i 인덱스를 늘릴지에 대한 답도 여기서 구했다. 만약 현재 위치하고 있는 index가 한번도 탐색을 안한 부분이고 해당 무기를 만들 수 있다면 dfs 를 그 자리에서 진행해주었다. 여기서 유의할 점은 만약에 저 if 문들에 else if 를 붙혀줬다면 정답은 못구했을거다. 그만큼 if와 elif 의 차이점은 잘 알아야겠다.
if 문이 통과한다면, 바로 shape 별로 visited 에 표시를 해주었고 해당 값을 cnt 에 추가해주며 최종값을 구하는걸로 답이 나왔다.
dfs 가 리턴이 된다면 visited 값을 원래 대로 돌려놓는것도 잊지 말아야한다.
배운점:
1. 2차원 벡터에서의 backtracking
2. 도형 끼워 맞추기
