[프로그래머스] 양과 늑대 - JAVA

문제링크 🚩

https://school.programmers.co.kr/learn/courses/30/lessons/92343?language=java

프로그래머스

 

 

​

📕 문제 접근 📕

- 모든 상황에 대해 DFS 순회가 가능하도록 설계 

• 해당 노드 방문 여부에 따른 Cnt 체크 
• sheepCnt가 wolfCnt보다 작거나 같은 경우 Return 
• 부모 노드 방문, 자식 노드 미방문 시 순회.

💻 Code 💻

class Solution {

    int[] copyInfo;
    int[][] copyEdges;
    int maxSheepCnt = 0;
    
    int SHEEP = 0;
    int WOLF = 1;

    public int solution(int[] info, int[][] edges) {
        copyInfo = info; // 총 길이
        copyEdges = edges;
        boolean[] visited = new boolean[info.length];
        dfs(0, visited, 0, 0);

        return maxSheepCnt;
    }

    public void dfs(int idx, boolean[] visited, int sheepCnt, int wolfCnt) {
        visited[idx] = true; // 방문 노드 체크
        // if (gInfo[idx] == 0)
        if (copyInfo[idx] == SHEEP) { // 양이라면 
            sheepCnt++;
            maxSheepCnt = Math.max(maxSheepCnt, sheepCnt);
        } else { // 늑대라면
            wolfCnt++;
        }

        if (sheepCnt <= wolfCnt) { // 늑대가 양보다 같거나 많으면 종료
            return;
        }

        for (int[] edge : copyEdges) { // 모든 상황에 대한 순회
            if (visited[edge[0]] && !visited[edge[1]]) { // 부모 노드는 방문했고, 자식 노드는 방문하지 않았을 때 
            	boolean[] nextVisited = deepCopyVisitedArray(visited);
                
                dfs(edge[1], nextVisited, sheepCnt, wolfCnt);
            }
        }
    }
    
    public boolean[] deepCopyVisitedArray(boolean array[]){
        boolean[] copyVisitedArray = new boolean[array.length];
            for (int i = 0; i < array.length; i++) {
                copyVisitedArray[i] = array[i];
        }
        return copyVisitedArray;
    }
}

 

 

 

💻 Code Review💻

- 코드 리펙터링 내용 

- 작은 단위의 함수화

# 최대 값을 갱신하는 Math.max 를 활용하여 가독성을 증대 시켰음

 maxSheepCnt = Math.max(maxSheepCnt, sheepCnt);
// if (sheepCnt > maxSheepCnt) {
 //     maxSheepCnt = sheepCnt;
// }
 

     
# 아래 반복문을 함수로 변경하였음
                
boolean[] nextVisited = new boolean[visited.length];
for (int i = 0; i < visited.length; i++) {
                	nextVisited[i] = visited[i];

boolean[] nextVisited = deepCopyVisitedArray(visited);

    public boolean[] deepCopyVisitedArray(boolean array[]){
        boolean[] copyVisitedArray = new boolean[array.length];
            for (int i = 0; i < array.length; i++) {
                copyVisitedArray[i] = array[i];
        }
        return copyVisitedArray;
    }
}

 

 

📖 배운 점📖