1931 - Painting a Grid With Three Different Colors
정보
- 문제 보기: 1931 - Painting a Grid With Three Different Colors
- 소요 시간: 💥1시간 초과
- 풀이 언어:
java
- 체감 난이도: 4️⃣
- 리뷰 횟수: ✅
풀이 키워드
스포주의
DP
비트마스킹
dfs
조합론
풀이 코드
정보
- 메모리: 55170 KB
- 시간: 255 ms
import java.util.*;
class Solution {
final int MOD = 1_000_000_007;
int m;
int n;
List<int[]> mColList;
List<List<Integer>> nxtColIdList; // list of mColList id list
Map<Integer, Integer> memo;
public long dp(int x, int prevColId) {
if (x == n) return 1;
int key = x << 10 | prevColId;
if (memo.containsKey(key)) return memo.get(key);
long res = 0L;
for (int id : nxtColIdList.get(prevColId)) {
res = (res + dp(x+1, id)) % MOD;
}
memo.put(key, (int)res);
return res;
}
public int colorTheGrid(int m, int n) {
this.m = m;
this.n = n;
mColList = new ArrayList<>();
nxtColIdList = new ArrayList<>();
memo = new HashMap<>();
// 1. dfs: pre-compute m-length columns
initMColList(new ArrayList<>(), 0);
// 2. pre-compute valid adj next columns for each m-length column
initNxtColIdList();
// 3. calc # of ways
long ans = 0L;
for (int id = 0; id < mColList.size(); ++id) {
ans = (ans + dp(1, id)) % MOD;
}
return (int) ans;
}
public void initMColList(List<Integer> data, int y) {
if (y == m) { // base case
int[] col = new int[m];
for (int i = 0; i < m; ++i) col[i] = data.get(i);
mColList.add(col);
return;
}
for (int c = 0; c < 3; ++c) { // iterate RGB
if (0 < y && data.get(y-1) == c) continue;
data.add(c);
initMColList(data, y+1);
data.remove(data.size()-1);
}
}
public void initNxtColIdList() {
for (int aid = 0; aid < mColList.size(); ++aid) {
nxtColIdList.add(aid, new ArrayList<>());
for (int bid = 0; bid < mColList.size(); ++bid) {
if (check(aid, bid)) {
nxtColIdList.get(aid).add(bid);
}
}
}
}
// check if b can be next to a
public boolean check(int aid, int bid) {
int[] a = mColList.get(aid);
int[] b = mColList.get(bid);
for (int i = 0; i < m; ++i) {
if (a[i] == b[i]) return false;
}
return true;
}
}
풀이 해설
단순 백트래킹은 TLE 터지는데 DP로 접근하자니 메모이제이션 적용하기 빡센 유형이다.
왜냐하면 메모이제이션을 위해 DP state를 '적당하게' 정의해야 하는데
현재 칸, 또는 인접 칸(위쪽, 왼쪽)의 칠해진 색을 state 정의로 사용하면 WA이기 때문이다.
❌ 실패한 발상
WA1
memo[i][c] -> ❌
각 칸의 번호를
i
로 정의할 때, 해당 칸에 색칠된 색을c
라고 하자.
특정 칸에 칠해진 색 뿐만 아니라 인접한 다른 칸의 색칠 상태가 경우의 수에 영향을 미치므로,
해당 state는 잘못된 정의이다.