Today I Learned

오늘 할일
1. LeetCode
2. 창엔 2일차
3. 창엔 일지작성
4. 기업 지원서 or 코테

오늘 한일
1. LeetCode

• 1466. Reorder Routes to Make All Paths Lead to the City Zero를 마저 디버깅해보려는데, 기존의 int[][]식의 관계표현은 MLE를 발생시켰다. 그래서 고안한게 이중 list를 사용해서 기존 int[][]의 메모리 낭비를 없애자는 취지였는데 간선의 방향성과 연속성을 보존해야하기에 쉽지 않았다. 근데 현재 문제에서의 관계 표현 방법인 아래는 상당히 효율적인 방식의 int[][]꼴의 관계표현으로 기억한다.

[[0,1],[1,3],[2,3],[4,0],[4,5]]

어떻게하면 이 관계들을 재귀를 이용해서 int[][]처럼 사용할 수 있을까?

상황을 간단하게 표현하고자 재귀를 recursive로 바꾸고 pop한 값에 대해 모든 connections를 순회하도록 코드를 짜보았다.

class Solution {

    public int minReorder(int n, int[][] connections) {
        //노드의 수 구하기
        int max_node=0;
        for(int i=0; i<connections.length; i++){
            if(max_node<connections[i][0])
                max_node=connections[i][0];
            if(max_node<connections[i][1])
                max_node=connections[i][1];
        }

        int result=0;
        Queue<Integer> queue=new LinkedList<Integer>();
        int[] visited=new int[max_node+1];

        queue.add(0);
        while(!queue.isEmpty()){
            int node=queue.remove();
            if(visited[node]==1)
                continue;
            visited[node]=1;
            for(int[] conn : connections){
                if(conn[0]==node){
                    if(visited[conn[1]]==1)
                        continue;
                    result++;
                    queue.add(conn[1]);
                } else if(conn[1]==node){
                    if(visited[conn[0]]==1)
                        continue;
                    queue.add(conn[0]);
                }
            }
        }
        return result;
    }
}

시간 최적화를 진행해보자