Programmers - 양과 늑대(Java)

https://programmers.co.kr/learn/courses/30/lessons/92343

코딩테스트 연습 - 양과 늑대

 

풀이

 

풀이에 필요한 변수 정의 및 초기화

탐색마다 갱신해야하는 최대 양의 수

해당 index의 자식 Node를 담고 있는 ArrayList배열

함수내에서 편하게 쓰기위한 입력값 info와 같은 값으로 전역변수 정의

// 전역 변수
static ArrayList<Integer>[] childs;
static int[] Info;
static int maxSheepCnt = 0;

 

해당 index의 자식 Node를 담고 있는 ArrayList배열 갱신

root 위치(0)에서 부터 dfs 탐색 시작

public static int solution(int[] info, int[][] edges) {
	Info = info;
	childs = new ArrayList[info.length];
	for (int[] l : edges) {
		int parent = l[0];
		int child = l[1];
		if (childs[parent] == null) {
			childs[parent] = new ArrayList<>();
		}
		childs[parent].add(child);
	}

	List<Integer> list = new ArrayList<>();
	list.add(0);
	dfs(0, 0, 0, list);
    
	return maxSheepCnt;
}

 

dfs탐색

현재위치에 따른 값 갱신(root위치(idx =0)에서 부터 시작)

• 현재위치 Node가 양/늑대인지에 따라 갯수 갱신
• 늑대의 수 >= 양의 수 인지 확인
• 해당 조건을 만족하면 양의 수가 0이 되므로 이 후의 dfs 탐색을 진행할 필요 X -> return
• 양의 최대값 갱신

 

다음 탐색 위치 찾기

• 이전 위치에서의 다음 탐색 Node들(매개변수) 복사/붙여넣기
• 다음 탐색 위치 중 현재 위치 제거
• List자료형의 remove사용하여 값을 탐색하여 제거할 때는 remove(Object형)이므로 remove(Integer.valueOf())와 같이 사용한다.
• 현재 Node의 자식을 다음 탐색 위치에 추가

 

모든 다음 탐색 위치에 대해 dfs실행 

private static void dfs(int idx, int sheepCnt, int wolfCnt, List<Integer> nextPos) {
	// 늑대/양 수, 양의 최대값 최신화
	if (Info[idx] == 0) sheepCnt++;
	else wolfCnt++;

	if (wolfCnt >= sheepCnt) return;
	maxSheepCnt = Math.max(sheepCnt, maxSheepCnt);

	// 다음 탐색 위치 갱신
	List<Integer> list = new ArrayList<>();
	list.addAll(nextPos);
	// 다음 탐색 목록중 현재 위치제외
	list.remove(Integer.valueOf(idx));
	if (childs[idx] != null) {
		for (int child : childs[idx]) {
			list.add(child);
		}
	}
	
	// 갈수 있는 모든 Node Dfs
	for (int next : list) {
		dfs(next, sheepCnt, wolfCnt, list);
	}
}

---

전체 코드

import java.util.*;

class Solution {
	// 해당 IDX의 자식은 누가 있는지
	static ArrayList<Integer>[] childs;
	static int[] Info;
	static int maxSheepCnt = 0;

	public static int solution(int[] info, int[][] edges) {
		Info = info;
		childs = new ArrayList[info.length];
		for (int[] l : edges) {
			int parent = l[0];
			int child = l[1];
			if (childs[parent] == null) {
				childs[parent] = new ArrayList<>();
			}
			childs[parent].add(child);
		}

		List<Integer> list = new ArrayList<>();
		list.add(0);
		dfs(0, 0, 0, list);
		return maxSheepCnt;
	}

	private static void dfs(int idx, int sheepCnt, int wolfCnt, List<Integer> nextPos) {
		// 늑대/양 수, 양의 최대값 최신화
		if (Info[idx] == 0) sheepCnt++;
		else wolfCnt++;

		if (wolfCnt >= sheepCnt) return;
		maxSheepCnt = Math.max(sheepCnt, maxSheepCnt);
   
		// 다음 탐색 위치 갱신
		List<Integer> list = new ArrayList<>();
		list.addAll(nextPos);
		// 다음 탐색 목록중 현재 위치제외
		list.remove(Integer.valueOf(idx));
		if (childs[idx] != null) {
			for (int child : childs[idx]) {
				list.add(child);
			}
		}
        
		// 갈수 있는 모든 Node Dfs
		for (int next : list) {
			dfs(next, sheepCnt, wolfCnt, list);
		}
	}
}