프로그래머스-모두 0으로 만들기

시행착오 1

-> 그래프를 행렬그래프를 통해서 풀어보자

class Solution {
    static int count = 0;
    public long solution(int[] a, int[][] edges) {
        int[][] map = new int[a.length][a.length];
        for(int i = 0 ; i < edges.length ; i++) {
            map[edges[i][0]][edges[i][1]] = 1;
            map[edges[i][1]][edges[i][0]] = 1;
        }
        for(int i = 0 ; i <edges.length ; i++){
	        logic(edges[0][1],a,map);            
        }

        for(int i = 0 ; i < a.length;i++){
            if(a[i] != 0){
                return -1;
            }
        }
        return count;
    }
    public long logic(int src, int[] weights, int[][] map){
        for(int i = 0 ; i < map.length ; i++){
            if(i != src && map[src][i] == 1){
                int nextSrc = i;
                map[src][nextSrc] = 0;
                map[nextSrc][src] = 0;
                long leafItem = logic(nextSrc, weights, map);
                weights[src] += leafItem;
                count+= leafItem;
                weights[nextSrc] = 0;
            }
        }
        return weights[src];
    }

}

메모리 초과가 엄청나다..

 

사유 : 방향 그래프라서, 행렬 그래프로 넣게되면 무방향 그래프가 되므로, 작성함

 

이걸 어떻게 해결할까 

 

시행착오 2.

Node 객체를 만들어서, 연결하고, 각 객체를 이동하면서 dfs 를 이용, 마지막 방문하는 노드부터 숫자를 더하는 방식으로 계산해보았다.

메모리 초과는 안된다.

 

메모리 초과 해결 방안

1. 연결하는 부분에 메모리를 쓰지 말아보자 -> node 의 생성을 한번만 가능하도록 처리하자

2.행렬 그래프는 사용하지 말자

 

시간초과가 엄청난다 

 

다음 방식은 어떤 방식으로 해야하나

import java.util.*;
class Solution {
    int count = 0;
    class Node {
        int node;
        int weight;
        boolean visit;
        List<Node> children;
        public Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
            this.visit = false;
            this.children = new ArrayList<>();
        }

        public boolean isVisit(){
            return this.visit;
        }

        public Node connectNode(List<Node> nodes, int[][] edges){
            for(int i=0 ; i < edges.length ; i++){
                if(edges[i][0] == this.node){
                    this.children.add(nodes.get(edges[i][1]));
                }
                if(edges[i][1] == this.node){
                    this.children.add(nodes.get(edges[i][0]));
                }
            }
            return this;
        }
        public void visit(){
            this.visit = true;
        }
    }
    public long solution(int[] a, int[][] edges) {
        int answer = 0;
        List<Node> nodes = new ArrayList<>(a.length);
        for(int i = 0 ; i < a.length ; i++){
            Node node = new Node(i, a[i]);
            nodes.add(node);
        }
        for(Node node : nodes){
        	node.connectNode(nodes, edges);
        }
        Node startNode = nodes.get(0);
        this.dfs(startNode);
        if(startNode.weight != 0) return -1;
        return count;
    }

    public void dfs(Node startNode){
        if(startNode.isVisit()){
            return;
        }
        startNode.visit();
        List<Node> children = startNode.children;
        for(Node node : children){
            if(node.isVisit()){
                continue;
            }
            dfs(node);
            count += node.weight;
            startNode.weight += node.weight;
            node.weight = 0;
        }
    }
}