[Java] LeetCode 2359. Find Closest Node to Given Two Nodes

[Java] LeetCode 2359. Find Closest Node to Given Two Nodes

 

문   제 : 

노드의 방향을 나타내는 정수형 1차원 배열 edges가 주어지고,

시작하는 노드 2개 node1 과 node2 가 주어졌을 때,
node1 과 node2 으로부터 공통적으로 접근할 수 있으며,

각각의 노드로부터의 거리가 최소로 될 수 있는 노드의 index 를 구하여라.

 

{ 2 <= edges.length <= 10^5 }

{ -1 <= edges[i] < edges.length }

{ edges[i] != i }

{ 0 <= node1, node2 <= edges.length }

 

 

Example )

Input: edges = [2,2,3,-1], node1 = 0, node2 = 1
Output: 2
Explanation: 
The distance from node 0 to node 2 is 1, and the distance from node 1 to node 2 is 1.
The maximum of those two distances is 1.
It can be proven that we cannot get a node with a smaller maximum distance than 1,
so we return node 2.

///////////////////////////////////////////////////////

Input: edges = [1,2,-1], node1 = 0, node2 = 2
Output: 2
Explanation: 
The distance from node 0 to node 2 is 2, and the distance from node 2 to itself is 0.
The maximum of those two distances is 2.
It can be proven that we cannot get a node with a smaller maximum distance than 2,
so we return node 2.

 

---

접   근 : 

DFS 를 이용해 방문 배열과 거리 배열을 만들어 각 노드의 방문을 처리하면서 거리를 업데이트 해준다.

 

 

---

해   결 : 

DFS를 통해 node1, node2 의 방문 배열과 거리 배열을 업데이트 시켜준다.

node1과 node2가 모두 방문 하였으며, 두 노드에서의 거리가 최대값이 되는 값을 구한다.

해당 값이 최소가 되게 업데이트해주고, 해당 노드를 리턴해준다.

 

DFS 함수 : 

node : 방문하려는 노드

edges[] : 주어진 간선 배열

distance[] : node1 or node2 부터 node까지의 거리를 저장하는 배열

visited[] : 방문 여부를 저장하는 배열

 

우선 방문처리를 해준다.

다음 노드가 있고, 방문한 적이 없으면 거리를 최신화 해주고 그 노드를 다시 방문한다.

 

---

DFS 함수 작성

 

 

public void dfs(int node, int[] edges, int[] distance, boolean[] visited) {
    visited[node] = true;
    int nextNode = edges[node];
    if (nextNode != -1 && !visited[nextNode]) { // 다음 노드가 존재하고, 방문하지 않았으면
        distance[nextNode] = distance[node] + 1; // 다음 노드로 가는 거리 = 현재까지 온 거리 + 1
        dfs(nextNode, edges, distance, visited);
    }
}

 

 

---

 

메인 솔루션 함수에서 필요한 배열들, 변수들 선언

 

int n = edges.length;
int ans = -1;
int minDis = Integer.MAX_VALUE;
int[] dis1 = new int[n];
int[] dis2 = new int[n];
boolean[] visited1 = new boolean[n];
boolean[] visited2 = new boolean[n];

 

---

 

DFS 함수를 돌리고, 거리의 최소값을 가지는 노드 반환

 

dfs(node1, edges, dis1, visited1);
dfs(node2, edges, dis2, visited2);

for (int currNode = 0; currNode < n; currNode++) {

    // 두 노드가 모두 방문하였고, 두 노드와 목표노드 사이의 거리의 최댓값이 최소가 되는 값이면
    if (visited1[currNode] && visited2[currNode] && minDis > Math.max(dis1[currNode], dis2[currNode])) { 
        minDis = Math.max(dis1[currNode], dis2[currNode]); // 최소거리 업데이트
        ans = currNode; // 최소거리가 되게 하는 목표노드 저장
    }
}
return ans;

 

 

---

결   과  :

class Solution {
    public void dfs(int node, int[] edges, int[] distance, boolean[] visited) {
        visited[node] = true;
        int nextNode = edges[node];
        if (nextNode != -1 && !visited[nextNode]) { // 다음 노드가 존재하고, 방문하지 않았으면
            distance[nextNode] = distance[node] + 1; // 다음 노드로 가는 거리 = 현재까지 온 거리 + 1
            dfs(nextNode, edges, distance, visited);
        }
    }

    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        int ans = -1;
        int minDis = Integer.MAX_VALUE;
        int[] dis1 = new int[n];
        int[] dis2 = new int[n];
        boolean[] visited1 = new boolean[n];
        boolean[] visited2 = new boolean[n];

        dfs(node1, edges, dis1, visited1);
        dfs(node2, edges, dis2, visited2);

        for (int currNode = 0; currNode < n; currNode++) {

            // 두 노드가 모두 방문하였고, 두 노드와 목표노드 사이의 거리의 최댓값이 최소가 되는 값이면
            if (visited1[currNode] && visited2[currNode] && minDis > Math.max(dis1[currNode], dis2[currNode])) { 
                minDis = Math.max(dis1[currNode], dis2[currNode]); // 최소거리 업데이트
                ans = currNode; // 최소거리가 되게 하는 목표노드 저장
            }
        }
        return ans;
    }
}