[프로그래머스/Java] 그래프_가장 먼 노드

문제

링크

 

 

Python 풀이

---

import collections

class Graph :
    def __init__(self):
        self.graph = {}
        self.listLength = 0
        self.results = {}
    
    def addGraph(self,left,right):
        g = self.graph
        leftExist = left in g.keys()
        if leftExist == False :
            g[left] = [left]
            self.listLength += 1
        
        temp = list(g[left])
        temp.append(right)
        g[left] = temp
             
        rightExist = right in g.keys()
        if rightExist == False :
            g[right] = [right]
            self.listLength +=1
            
        temp = list(g[right])
        temp.append(left)
        g[right] = temp

    def __str__(self):
        print("node num : ",self.listLength)
        graph = self.graph
        keys = list(graph.keys())
        
        for k in keys :
            print(k,":",graph[k])
        
    def findFartestNode(self) :
        
        graph = self.graph
        self.graph = collections.OrderedDict(sorted(graph.items()))
        
        do = [1]
        visited = [False] * (self.listLength+1)
        visited[1] = True
        answer = [0] * (self.listLength+1)
        
        while len(do) != 0 :
            
            ci = do.pop(0)
            
            for i in range(1,len(graph[ci])) :
                cn = graph[ci][i]
                #print("start index : ",ci)
                 
                if visited[cn] == False :
                    visited[cn] = True
                    answer[cn] = answer[ci]+1
                    do.append(cn)
                
        return answer.count(max(answer))
        
def solution(n, nodes):

    g = Graph()

    for node in nodes : 
        g.addGraph(node[0],node[1])

    return g.findFartestNode()

---

(이거 쓰는데 6시간 걸렸다는건 안비밀 .. 한번 해봤더니 그래도 다음은 잘 되더라 ^^)

가장 멀리 연결되어있는 노드를 찾는 문제다. 가장 먼친구들 한꺼번에 = 가까운데 있는 노드들 하나씩 검사해서 처리하기 = bfs. 양방향으로 연결되어 있는 노드들이라 dfs를 쓰면 안될것 같다. 최소거리를 가늠하기 어렵고 bfs로 하면 한 엣지씩 처리하기 때문에 최소거리로 탐색할 수 있을 듯 하다.

 

아 사실 햇갈린다 ㅋㅋㅋ dfs, bfs 쓰임 다시 검색해보자. bfs는 큐, dfs는 스택 기억하기!

 

 

 

 

 

 

 

 

 

1. Main부분

---

def solution(n, nodes):

    g = Graph()

    for node in nodes : 
        g.addGraph(node[0],node[1])

    return g.findFartestNode()

---

노드를 인자값으로 전달해 그래프를 만들어주자

 

 

 

 

 

 

 

 

2. Class Graph 부분

---

def __init__(self):
  self.graph = {}
  self.listLength = 0
  self.results = {}

---

Since, it is Python, I'm going to user Dictionary for Graph Implementation.

 

 

 

---

 def addGraph(self,left,right):
        g = self.graph
        
    	//left값이 그래프에 있는지 확인하고 있으면 불러와서 오른쪽 값을 붙인다.
        leftExist = left in g.keys()
        if leftExist == False :
            g[left] = [left]
            self.listLength += 1
        
        temp = list(g[left])
        temp.append(right)
        g[left] = temp
         
        //right값이 그래프에 있는지 확인하고 있으면 불러와서 왼쪽 값을 붙인다.
        rightExist = right in g.keys()
        if rightExist == False :
            g[right] = [right]
            self.listLength +=1
            
        temp = list(g[right])
        temp.append(left)
        g[right] = temp

---

Above code eixist for add nodes to exist Graph. Now i think this implementation is not best for any reason .. These are appealed with this format

{1 : [0,1,2, .. ] , 2: [2,3,4,] }

It seems more .. like .. very look .. ugly. I think i must better if i just use double integer array.

 

 

 

 

 

 

---

def findFartestNode(self) :
        
        graph = self.graph
        
        //시간 단축을 위해서 sort 진행
        self.graph = collections.OrderedDict(sorted(graph.items()))
        
        //queue를 사용, 시작은 1
        do = [1]
        visited = [False] * (self.listLength+1)
        visited[1] = True
        answer = [0] * (self.listLength+1)
        
        while len(do) != 0 :
            
            ci = do.pop(0)
            
            //여기가 핵심!! 지금 판단하려는 노드와 연결되어 있다면 정답 array에 1씩 증가시킨다.
             for i in range(1,len(graph[ci])) :
                cn = graph[ci][i]
                 
                if visited[cn] == False :
                    visited[cn] = True
                    
                    //이러면 노드당 1부터 거리가 저장된다.
                    answer[cn] = answer[ci]+1
                    do.append(cn)
                
        return answer.count(max(answer))

 

---

1부터 노드를 차근차근 탐색하며 연결되어 있다면 이전 1부터의 거리에 1을 더해서 정답 array에 저장한다. 예를들어 1 : [2,3]일때 정답 array [0,0,0]은 탐색후 [0,1,1]이 되고 2,3은 큐로 다시 들어와서 각각 연결된 노드들에게 자신과 1의 거리인 1에 1을 더한 값인 2의 거리를 전달하고 해당 array에 값이 저장되게 된다.

 

문제에서 가장 멀리있는 노드의 갯수를 전달하라고 했으므로 max의 갯수를 세어서 return 해주면 된다.

 

 

 

 

 

 

 

 

 

Java 풀이

---

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
		n++;
		
		int[] dist = new int[n];
		boolean[][] connect = new boolean[n][n];
		
		for(int[] e : edge) 
			connect[e[0]][e[1]] =connect[e[1]][e[0]]=true;
		
		Queue<Integer> queue = new LinkedList();
		queue.add(1);
		dist[1]=1;
		
		while(!queue.isEmpty()) { 
			int front = queue.poll(); 

			for(int i=1;i<n;i++)
				if(dist[i]==0 && connect[front][i]) {
					dist[i]=dist[front]+1;
					queue.offer(i);
					
				}
		}
		
		int result = 0;

		for(int i=1;i<n;i++) {
			if(Arrays.stream(dist).max().getAsInt()==dist[i]) {
				result++;
			}
		}
        
        return result;
    }
}

---

자바는 파이썬 보다 더 간단히 풀었다. ㅋㅋㅋ 파이썬이랑 비교해보면 그리 알고리즘이 다르지 않지만 .. 파이썬은 graph에 node를 추가하는 부분을 어렵게 생각해서 더 어려웠던것 같다 ㅠㅠ.

 

여기서 내가 유용하게 사용한코드는 Arrays ~ getAsInt 부분인데 이 한줄이면 거창한 for문 사용 없이 해당 array에서 최고값을 가져올 수 있다. 개이득 👍