[Java/2022 KAKAO BLIND RECRUIT] 양과 늑대

Jake·2022년 2월 11일
0

PS

목록 보기
1/14

사용한 알고리즘

  • 비트마스크
  • 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);
					}
				}
			}
		}
	}

Process

  • 비트마스크

    boolean[][] visited = new boolean[1<<n][n+1]

    DFS에서 방문 여부를 체크하기 위해 2차원 배열 visited를 선언합니다.
    1<<n은 비트마스크, n+1은 (양 - 늑대) 값을 나타내는 것으로 했습니다.


  • HashMap
    HashMap<> adj는 간선 정보를 의미합니다.

  • DFS
    문제의 하이라이트라고 할 수 있는 부분인 것 같습니다.
    하지만 하나하나 뜯어보면, 딱히 복잡할 것도 없는 코드입니다.
    대략적인 로직은 다음과 같습니다.


  1. 방문 체크
		for(int i = 0; i < n; i++) {//0번 ~ n-1번 노드에 대해 반복
			if((bitmask & 1<<i) > 0) {

현재 dfs 상태에서 방문 중인 노드를 찾는 과정입니다.
현재 노드가 bitmask에서 켜져있다면, if문을 true로 통과할 수 있습니다.

  1. 갈 수 있는 노드 탐색

    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);
    	}
    }

list를 사용한 코드

위 코드에서 반복문으로 비트마스크가 켜져있는 것이 조금 비효율적으로 느껴져서, 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);
				}
			}
		}
	}  
}
profile
Java/Spring Back-End Developer

0개의 댓글