프로그래머스 - 가장 먼 노드(Level 3)/Wanna Be 컴잘알

출처 - https://programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스

-문제-

 

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

 

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

 

-접근-

1. grpah를 표현할 수 있는 벡터를 새로 만들어 주기 위해서 몇 개의 노드가 있는지 노드갯수먼저 찾았다.

2. 노드 갯수를 찾은 후 graph.resize()를 사용하여 그래프 메모리 확보

3. bfs를 사용하여 1번 노드에서 이동했을 때, 가장 먼 노드이면서 최소 비용인 노드가 몇개인지 cnt와 prev를 통해 기록하여 return해주었다.

 

-코드-

 

c++

#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;

// 1. n개의 노드가 있는 그래프 존재(1~n의번호)
// 2. 최단경로로 이동했을 때, 가장 많은 간선을 지난 노드의 개수를 구하여라
// 3. 시작점에 따라 결과가 달라진다.

vector <vector<int>> graph;

int search_cnt(int number) {
	bool check[20000];
	memset(check, false, sizeof(check));
	
	queue <int> q;
	q.push(number);
	check[number] = true;

	int prev = 0;

	while (1) {
		int loop = q.size();
		int cnt = 0;

		for (int i = 0; i < loop; i++) {
			int cur_number = q.front();
			q.pop();

			for (int k = 0; k < graph[cur_number].size(); k++) {
				if (check[graph[cur_number][k]] == false) {
					check[graph[cur_number][k]] = true;
					q.push(graph[cur_number][k]);
					cnt += 1;
				}
			}
		}

		if (q.empty()) {
			break;
		}
		prev = cnt;
	}

	return prev;
}


int solution(int n, vector<vector<int>> edge) {
	int answer = 0;

	int max_number = 0;
	for (int i = 0; i < edge.size(); i++) {
		max_number = max(max_number, edge[i][0]);
		max_number = max(max_number, edge[i][1]);
	}

	graph.resize(max_number);

	for (int i = 0; i < edge.size(); i++) {
		graph[edge[i][0] - 1].push_back(edge[i][1] - 1);
		graph[edge[i][1] - 1].push_back(edge[i][0] - 1);
	}

	answer = max(answer, search_cnt(0));
	
	return answer;
}

 

java

 

package saa;

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    
	static boolean connect[][];
	static boolean check[];
	
	int bfs(Queue<Integer> q, int n) {
		int countCity=0;
		
		while(!q.isEmpty()) {
			int loop = q.size();
			
			for(int index=0; index<loop;index++) {
				int cur = q.poll();
				
				for(int i=0; i<n;i++) {
					if(connect[i][cur] && !check[i]) {
						check[i] = true;
						q.add(i);
					}
				}
			}
			countCity = loop;
		}
		
		return countCity;
	}
	
	public int solution(int n, int[][] edge) {
          int answer = 0;

          connect = new boolean[n][n];
          check = new boolean[n];

          for(int index=0; index<edge.length; index++) {
              connect[edge[index][0]-1][edge[index][1]-1] = true;
              connect[edge[index][1]-1][edge[index][0]-1] = true;
          }

          Queue<Integer> q = new LinkedList<>();

          q.add(0);
          check[0] = true;
        
        
          answer = bfs(q, n);
        
        return answer;
    }
}

Python

from collections import deque

def bfs(vector, check, start):
    answer = 0
    check[start] = True

    dq = deque()
    for value in vector[start]:
        dq.appendleft(value)
        check[value] = True
    
    while len(dq) !=0 :
        loop = len(dq)
        for i in range(loop):
            curnode = dq.pop()
            for value in vector[curnode]:
                if check[value] == False:
                    check[value] = True
                    dq.appendleft(value)
        answer = loop
    return answer


def solution(n, edge):
    answer = 0
    check = [ False for row in range(20001) ]
    vector = [[] for i in range(20001)]


    for i,value in enumerate(edge):
        edge1= value[0]
        edge2= value[1]
        vector[edge1].append(edge2)
        vector[edge2].append(edge1)

    answer = bfs(vector,check ,1)
    return answer