Today I Learned

오늘 할일
1. LeetCode
2. 창엔 1일차
3. 취업지원서 작성
4. 창엔 보고서 작성

오늘 한일
1. LeetCode

• 1466. Reorder Routes to Make All Paths Lead to the City Zero는 모든 도시에서 수도로 향하는 길의 방향을 최소로 몇번 바꿔야 모든 노드가 수도에 도달할 수 있는지를 묻는 문제이다.

/*
n개의 도시를 연결하는 오로지 하나의 길이 존재한다. 두 도시 사이는 너무 좁아서 한방향의 길만 존재한다.
connectinos[i]=[a,b]는 a->b를 의미한다.
올해에 수도인 0번째 도시에 행사가 있어 많은 사람들이 와야한다.
네 업무는 몇가지 길의 방향을 바꾸어 모든 도시가 수도에 방문할 수 있게해야한다.
이때 길의 방향을 최소로 바꾸는 횟수를 리턴하시오.

특징
1. 모든 노드에서 0번 노드에 접근할 수 있어야 한다
2. 방향을 신경쓰지 않는다면 모든 노드는 0번 노드에 접근할 수 있다.
3. 모든 노드에서 0번 노드로 접근하기 위한 루트들을 저장하고, 방향 전환이 필요한 경우를 중복없이 센다.

접근방법
1. 2차원 배열을 이용하여 단방향 관계를 구현한다.
2. 방향성을 없앤 관계를 이용하여 각 노드에서 노드0으로 접근하기 위한 경로를 찾아낸다.
3. 해당 경로에서 방향성때문에 접근하지 못하는 노드의 개수를 중복없이 센다.

잠시만. 역으로 발상하자. n의 개수가 주어지니, 0에서부터 해당 노드까지 접근하는 방식이 더 효율적이다.
방향관계는 0에서부터 모든 노드에 접근하는 방향을 지향하게끔 코드를 작성하겠다.
 */
class Solution {
    private int[][] relations;
    private int size;
    private int[] visited;
    private int change_count=0;

    private void traversal(int node){
        //탈출조건
        if(visited[node]==1)
            return;

        //현재노드 방문처리
        visited[node]=1;
        for(int i=0; i<size; i++){
            if(relations[node][i]==1){//node->i로 접근이 가능한 경우
                //방향전환
                change_count++;
                traversal(i);
            }
            
            if(relations[i][node]==1){//i->node로 접근이 가능한 경우
                relations[i][node]=0;
                relations[node][i]=1;
                traversal(i);
            }
        }
    }

    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];
        }
        this.size=max_node+1;
        
        //필요한 배열 초기화
        this.relations=new int[size][size];
        this.visited=new int[size];

        //관계
        for (int[] elem : connections)
            relations[elem[0]][elem[1]]=1;
        
        traversal(0);
        return change_count;
    }
}

로 문제에서 주어진 connections[][]를 relations[][]로 바꾸어 노드간 관계를 배열꼴로 처리해보았다.

방법은 맞았지만 MLE가 발생한 것으로 보아 문제에서 주어진 connections를 최대한 사용해야하는 듯 하다.