[Programmers] 격자 뒤집기 미로

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/389630

프로그래머스

 

비트마스크를 통해 풀 수 있는 문제였습니다.

 

알고리즘은 다음과 같습니다.

1. 격자의 모든 칸의 visible 값을 더해 기본 점수를 구하고, 각 칸에서 hidden과 visible의 차이를 diff로 계산합니다.

 

2. 각 행을 뒤집거나 그대로 두는 모든 경우 {2^(행 수}) 가지를 고려하여, 뒤집힌 행의 수에 따른 비용을 기본 점수에서 차감해 기준 점수를 정합니다.

 

3. 각 열에서 "열을 그대로 둘 때”와 “열을 뒤집을 때”의 추가 이득과, 체스판에서 홀수 위치 셀의 최소 점수를 각각 계산합니다.

• 각 열을 처리할 때는 두 가지 선택지가 있음
  • 열을 그대로 둘 때는 해당 열에서 행 상태에 따라, 뒤집힌 행의 경우에는 diff가 적용되어 추가 이득이 생기고, 뒤집히지 않은 행은 변화가 없으므로 그 셀의 값은 그대로 유지
  • 열을 뒤집을 때는 반대로 뒤집히지 않은 행에만 diff가 적용되며, 뒤집힌 행은 변화가 없으므로 이득이 생기지 않는데, 여기에 열을 뒤집는 비용 k가 추가로 차감됨

 

• 해밀턴 경로가 불가능할 경우 한 칸을 빼야 하므로 각 열의 체스판 홀수 위치에 있는 셀들의 점수를 계산
  • 행이 뒤집혔고 열이 뒤집히지 않았을 때 홀수 셀의 점수는 visible+diff가 되고, 열이 뒤집혔을 때는 visible만 적용
  • 반면 행이 뒤집히지 않았다면 위 두 경우가 반대로 적용

 

4. 전체 격자에서 모든 칸을 방문할 수 있는지, 즉 해밀턴 경로가 가능한지 여부를 판단합니다.

 

5. 해밀턴 회로가 가능하면 각 열을 뒤집었을 경우와 뒤집지 않았을 경우를 비교했을 때 더 큰 이득을 선택하면 됩니다.

 

5.1 해밀턴 경로가 불가능한 경우에는 모든 칸을 방문할 수 없으므로, 한 칸의 홀수 위치 셀을 경로에서 제외해야 합니다.

이때 최종 점수는 기준 점수와 각 열에서 선택된 옵션들의 이득 합계에서, 선택된 옵션들의 홀수 위치 셀 값들 중 전역 최소값을 빼서 계산됩니다.

• 문제는, 만약 한 열에서 선택된 옵션의 홀수 점수가 지나치게 낮을 경우 해당 열이 전체 전역 최소 홀수 점수를 결정하게 되어 최종 점수에서 큰 페널티가 발생
• 단순히 각 열에서 최고 profit 옵션만 선택하면, 낮은 홀수 점수가 포함되어 전역 최소값이 낮아지고, 최종 점수가 떨어질 위험 존재
• 위 두 문제를 해결하기 위해 threshold 개념을 도입 (코드 주석 참고)

 

6. 모든 행 뒤집기 경우에서 산출된 최종 점수 중 가장 큰 값을 결과로 반환합니다.

 

 

개발환경: Programmers IDE   

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~