강의로 돌아가기
[JAVA] 정답 코드
문제의 갈피를 못잡고 있다가 다른 분들의 힌트를 보고 풀었습니다.
가장 위의 행의 모든 경우에 대해 아랫줄은 윗줄이 0이 되도록만 하는 모델입니다.
결국 첫번째 행의 경우만 알면 나머지 행은 모두 종속되어있어서 탐색 범위를 매우 좁힐 수 있습니다.
탐색이야 여러가지 방법이 있겠지만 저는 비트마스킹을 썼습니다.
다만 상태가 0 또는 1인 2가지가 아니라 0 ~ 3인 4가지입니다. (0번 ~ 3번 회전)
그래서 각 셀마다 2개의 비트를 할당해 00, 01, 10, 11의 4가지 상태를 뽑을 수 있게 됐습니다.
또한 이 경우엔 모든 경우를 사용하기 때문에 더욱 효율적인 탐색법이라고 생각합니다.
나머지 부분은 평범하게 해결하였습니다.
class Solution {
int[] dx = {0, -1, 1, 0, 0};
int[] dy = {0, 0, 0, -1, 1};
public int solution(int[][] clockHands) {
int min = 200;
int n = clockHands.length;
int[][] spinMap = new int[n][n]; // 각 칸의 누적 회전 상태 기록
// 첫 줄 회전 조합을 비트마스크로 완전탐색 (2비트 * n칸 = 4^n)
Outter : for (int spins = 0; spins < (1 << (2 * n)); spins++) {
Arrays.stream(spinMap).forEach(row -> Arrays.fill(row, 0));
int sum = 0;
// 첫 줄은 회전 조합으로, 나머지 줄은 위쪽 시계를 12시로 맞추기 위한 회전 유도
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
int spin = row == 0
? (spins >> (col * 2)) & 3
: (4 - ((clockHands[row - 1][col] + spinMap[row - 1][col]) & 3)) & 3;
// 회전 시 자신과 인접 시계에 영향 적용
for (int i = 0; i < 5; i++) {
int nx = row + dx[i];
int ny = col + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
spinMap[nx][ny] = (spinMap[nx][ny] + spin) & 3;
}
}
sum += spin;
if (sum >= min) continue Outter; // pruning
}
}
// 마지막 줄이 모두 12시 방향인지 확인
for (int col = 0; col < n; col++) {
if (((clockHands[n - 1][col] + spinMap[n - 1][col]) & 3) != 0) continue Outter;
}
min = Math.min(min, sum);
}
return min;
}
}
답변 쓰기