[Leetcode(릿코드)] 997. Find the Town Judge (Easy)

URL)

https://leetcode.com/problems/find-the-town-judge/

 

문제)

마을에 1~N으로 라벨링된 N명의 사람들이 있는데,

한 소문으로 (비밀적으로) 1명이 마을의 판사다

 

만약, 마을의 판사가 존재한다면 

1. 마을 판사는 아무도 신뢰하지 않는다

2. 모든 사람(판사는 제외)은 마을 판사를 신뢰

3.(1,2)를 만족하는 사람은 정확히 1명이다

trust[i] = [a,b] 주어지면 a가 b를 신뢰한다는 뜻이다

만약 마을 판사가 존재하고 신원을 확인할 수 있는 경우

마을 판사의 라벨을 반환하고, 

그렇지 않으면 -1을 반환하라

---

해결)

이 문제는 그래프를 이용해 풀었다.

화살표는 신뢰도이다 (1->2) : 1이 2를 신뢰한다 

한번 그림과 결과를 보면서 예를 들어보자.

 

Input: N = 2, trust = [[1,2]]
Output: 2

1,2,3번 조건을 만족하는 사람이 2번이므로 2번이 마을 판사이다

 

Input: N = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

1번 조건이 맞지 않으므로 -1을 리턴한다 (마을 판사는 아무도 신뢰해서는 안된다)

 

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3

3번은 아무도 신뢰하지 않고, 모두가 3번을 신뢰한다. 그 사람은 3번 1명뿐이니 3번이 마을 판사이다

 

그러면 이제 코드로 하나씩 표현해보자

1. 노드 정의

위 그림에서 사람 객체를 정의한다

각 사람은 label 되어 있으니 변수 label을 정의하고,

사람을 라벨 번호로 구분해주기 위해 equals와 hasCode를 재정의한다. 

public class Vertex {
  int label;

  public Vertex(int label) {
    this.label = label;
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) {
      return true;
    }
    if (o == null || getClass() != o.getClass()) {
      return false;
    }
    Vertex vertex = (Vertex) o;
    return Objects.equals(label, vertex.label);
  }

  @Override
  public int hashCode() {
    return Objects.hash(label);
  }
}

2. 그래프 정의

자신을 신뢰하는 사람들을 받을 inDegreeVertices와 자신이 신뢰하고 있는 사람들을 받을 outDegreeVertices를 정의한다

class Graph {
  private Map<Vertex, List<Vertex>> inDegreeVertices;
  private Map<Vertex, List<Vertex>> outDegreeVertices;

  public Graph() {
    this.inDegreeVertices = new HashMap<>();
    this.outDegreeVertices = new HashMap<>();
  }

  public Map<Vertex, List<Vertex>> getInDegreeVertices() {
    return inDegreeVertices;
  }

  public void setInDegreeVertices(Map<Vertex, List<Vertex>> inDegreeVertices) {
    this.inDegreeVertices = inDegreeVertices;
  }

  public Map<Vertex, List<Vertex>> getOutDegreeVertices() {
    return outDegreeVertices;
  }

  public void setOutDegreeVertices(Map<Vertex, List<Vertex>> outDegreeVertices) {
    this.outDegreeVertices = outDegreeVertices;
  }

  void addVertex(int label) {
    inDegreeVertices.putIfAbsent(new Vertex(label), new ArrayList<>());
    outDegreeVertices.putIfAbsent(new Vertex(label), new ArrayList<>());
  }

  void addEdge(int label1, int label2) {
    Vertex v1 = new Vertex(label1);
    Vertex v2 = new Vertex(label2);
    outDegreeVertices.get(v1).add(v2);
    inDegreeVertices.get(v2).add(v1);
  }
}

3. 신뢰(엣지)를 연결하여 답을 구한다 

결국 구하고자 하는 답은 내가 신뢰하는 사람들은 0명이고 나를 신뢰하는 사람들은 N-1명이다

즉, outDegreeVertices 안의 리스트의 개수는 0 && inDegreeVertices 안의 리스트 개수는 N-1이 존재하면 

그 사람의 label을 반환하고 아니면 -1을 반환하면 된다

class Solution {
    public int findJudge(int N, int[][] trust) {
	    
	    int result = -1;
	
	    Graph graph = new Graph();
	    for (int i=1; i<=N; i++) {
	      graph.addVertex(i);
	    }
	
	    for (int i=0; i<trust.length; i++) {
	      int start = trust[i][0];
	      int end = trust[i][1];
	      graph.addEdge(start, end);
	    }
	
	    Map<Vertex, List<Vertex>> inDegreeVertices =  graph.getInDegreeVertices();
	    Map<Vertex, List<Vertex>> outDegreeVertices =  graph.getOutDegreeVertices();
	
	    for (Vertex key : outDegreeVertices.keySet()) {
	      if(outDegreeVertices.get(key).size() == 0 && inDegreeVertices.get(key).size() == N-1) {
	        result = key.label;
	      }
	    }
	
	    return result;
    }
}

 

이렇게 Java로 그래프 문제를 풀어보았다