본문으로 건너뛰기

2359 - Find Closest Node to Given Two Nodes

정보

풀이 키워드​

스포주의

bfs


풀이 코드​

정보
  • 메모리: 56300 KB
  • 시간: 16 ms
class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        final int n = edges.length;
        int[] dist1 = new int[n];
        int[] dist2 = new int[n];
        Arrays.fill(dist1, -1);
        Arrays.fill(dist2, -1);

        Deque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{node1, 0});
        dist1[node1] = 0;
        while (!q.isEmpty()) {
            int[] e = q.poll();
            int s = e[0];
            int v = e[1];
            int t = edges[s];
            if (t == -1) break; // no outgoing node
            if (dist1[t] != -1) break; // already visited
            dist1[t] = v + 1;
            q.add(new int[]{t, v+1});
        }

        q = new ArrayDeque<>();
        q.add(new int[]{node2, 0});
        dist2[node2] = 0;
        while (!q.isEmpty()) {
            int[] e = q.poll();
            int s = e[0];
            int v = e[1];
            int t = edges[s];
            if (t == -1) break; // no outgoing node
            if (dist2[t] != -1) break; // already visited
            dist2[t] = v + 1;
            q.add(new int[]{t, v+1});
        }

        int ans = -1;
        int mn = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            if (dist1[i] == -1 || dist2[i] == -1) continue;

            int res = Math.max(dist1[i], dist2[i]);
            if (res < mn) {
                mn = res;
                ans = i;
            }
        }

        return ans;
    }
}

풀이 해설​

node1, node2에 대해 각각 bfs를 돌려서 거리를 구하고

문제에서 주어진 조건에 따라 가장 적합한 거리를 리턴해야 하는 문제이다.

bfs 2번 + 최적해 스캔 로직을 합해서 T(3n)=O(n)T(3n) = O(n)의 시간복잡도를 가지게 된다.

사이클이 있을 수 있다고 명시되어있기 때문에 visited 처리가 필수이다. (명시 안해도 처리해야되긴 함)


경고

난독증 주의​

Return the index of the node that can be reached from both node1 and node2, such that the maximum between the distance from node1 to that node, and from node2 to that node is minimized.


영어 지문을 잘 읽어야 한다. 구조화를 좀 해보자면 이렇게 정리된다.

Return the maximum distance between (
    from node1 to that node,
    from node2 to that node
)
which is minimized.

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

코드로 나타내자면 min(max(dist1, dist2)) 를 구하라는 것이다.

구하고자 하는 값이 무슨 의미일까? 하고 생각해보면, node1 -> node <- node2 의 상태에서

node1과 node2 양 측과의 거리가 가장 가까운걸 구하라는 의미이다.


"node1, node2와의 거리가 최소여야 한다고? 그럼 두 거리 더해서 최소가 되는걸로 리턴하면 되지 않음??"

...이라고 생각하는 사람들이 WA를 받도록 문제가 설계되어있다.

index 0) dist1 = 0, dist2 = 2
index 1) dist1 = 1, dist2 = 1

만약 이렇게 dist 배열이 계산되었다면, 정답은 1번 인덱스지만

min(dist1 + dist2) 개념으로 접근했다면 0번 인덱스를 리턴하게 되어 WA이다.

그래서 문제에서 하라는 그대로 로직을 작성하는 것이 중요하다.


메모​

  • 이 문제도 처음에 너무 복잡하게 생각함
    • 두 거리를 동시에 처리하는, 내가 모르는 방법이 있나? 하는 의심이 문제인듯