- 비트마스크
- DFS
class Solution {
int[] info;
int maxCnt = 1;
int n;
boolean[][] visited;
HashMap<Integer, ArrayList<Integer>> adj;
public int solution(int[] info, int[][] edges) {
this.info = info;
n = info.length;
visited = new boolean[1<<n][n+1];
adj = new HashMap<>();
for(int[] edge : edges) {
adj.computeIfAbsent(edge[0], key -> new ArrayList<>()).add(edge[1]);
adj.computeIfAbsent(edge[1], key -> new ArrayList<>()).add(edge[0]);
}
visited[1][1] = true;
ArrayList<Integer> initial = new ArrayList<>();
initial.add(0);
dfs(initial, 1, 1, 0);
return maxCnt;
}
public void dfs(int bitmask, int sheep, int wolf) {
maxCnt = Math.max(maxCnt, sheep);
int cnt = sheep - wolf;
for(int i = 0; i < n; i++) {
if((bitmask & 1<<i) > 0) {
ArrayList<Integer> canGo = adj.get(i);
for(int e : canGo) {
int newBitmask = bitmask | (1<<e);
int nSheep = sheep;
int nWolf = wolf;
if((bitmask & 1<<e) == 0) {
if(info[e] == 0) nSheep++;
else nWolf++;
}
int newCnt = nSheep - nWolf;
if(newCnt <= 0) continue;
if(!visited[newBitmask][newCnt]) {
visited[newBitmask][newCnt] = true;
dfs(newBitmask, nSheep, nWolf);
}
}
}
}
}
비트마스크
boolean[][] visited = new boolean[1<<n][n+1]
DFS에서 방문 여부를 체크하기 위해 2차원 배열 visited를 선언합니다.
1<<n은 비트마스크, n+1은 (양 - 늑대) 값을 나타내는 것으로 했습니다.
HashMap
HashMap<> adj는 간선 정보를 의미합니다.
DFS
문제의 하이라이트라고 할 수 있는 부분인 것 같습니다.
하지만 하나하나 뜯어보면, 딱히 복잡할 것도 없는 코드입니다.
대략적인 로직은 다음과 같습니다.
for(int i = 0; i < n; i++) {//0번 ~ n-1번 노드에 대해 반복
if((bitmask & 1<<i) > 0) {
현재 dfs 상태에서 방문 중인 노드를 찾는 과정입니다.
현재 노드가 bitmask에서 켜져있다면, if문을 true로 통과할 수 있습니다.
갈 수 있는 노드 탐색
ArrayList<Integer> canGo = adj.get(i);//노드 i에서 갈 수 있는 노드들
for(int e : canGo) {
int newBitmask = bitmask | (1<<e); //새 비트마스크
int nSheep = sheep;
int nWolf = wolf;
if((bitmask & 1<<e) == 0) {//방문할 노드가 양인지, 늑대인지 체크
if(info[e] == 0) nSheep++;
else nWolf++;
}
int newCnt = nSheep - nWolf;
if(newCnt <= 0) continue; //양-늑대 조건을 만족하지 않으면 더이상 진행하지 않습니다
if(!visited[newBitmask][newCnt]) {//방문하지 않았다면
visited[newBitmask][newCnt] = true;
dfs(newBitmask, nSheep, nWolf);
}
}
위 코드에서 반복문으로 비트마스크가 켜져있는 것이 조금 비효율적으로 느껴져서, ArrayList를 사용하여 개선한 코드입니다.
하지만 ArrayList를 생성하고, add하는 과정에서 또 시간이 소요되기 때문에 큰 차이는 없을 것 같습니다.
class Solution {
int[] info;
int maxCnt = 1;
int n;
boolean[][] visited;
HashMap<Integer, ArrayList<Integer>> adj;
public int solution(int[] info, int[][] edges) {
this.info = info;
n = info.length;
visited = new boolean[1<<n][n+1];
adj = new HashMap<>();
for(int[] edge : edges) {
adj.computeIfAbsent(edge[0], key -> new ArrayList<>()).add(edge[1]);
adj.computeIfAbsent(edge[1], key -> new ArrayList<>()).add(edge[0]);
}
visited[1][1] = true;
ArrayList<Integer> initial = new ArrayList<>();
initial.add(0);
dfs(initial, 1, 1, 0);
return maxCnt;
}
public void dfs(ArrayList<Integer> list, int bitmask, int sheep, int wolf) {
maxCnt = Math.max(maxCnt, sheep);
int cnt = sheep - wolf;
for(int s : list) {
ArrayList<Integer> canGo = adj.get(s);
for(int e : canGo) {
int newBitmask = bitmask | (1<<e);
int nSheep = sheep;
int nWolf = wolf;
if((bitmask & 1<<e) == 0) {
if(info[e] == 0) nSheep++;
else nWolf++;
}
int newCnt = nSheep - nWolf;
if(newCnt <= 0) continue;
if(!visited[newBitmask][newCnt]) {
visited[newBitmask][newCnt] = true;
ArrayList<Integer> newList = new ArrayList<>();
newList.addAll(list);
newList.add(e);
dfs(newList, newBitmask, nSheep, nWolf);
}
}
}
}
}