12/10 풀이

Redundant Connection

https://neetcode.io/problems/redundant-connection

NeetCode

 

이 문제와 비슷한 느낌을 받았다.
https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

실제로, 비슷하게 풀이하여 정답을 맞출 수 있었다.

처음부터 각 노드의 연결된 간선을 끊어주며, 끊어졌을 때 모든 노드를 방문할 수 있다면 정답으로, 아니라면 skip을 해주었다. 모든 노드를 방문했을 때, 가장 뒤에 등장한 노드를 리턴해줘야 했으므로 값을 계속 갱신해줬다.

헷갈렸던 부분은 연결된 노드를 끊을 때 였는데,

graph.get(u).remove((Integer)v);
graph.get(v).remove((Integer)u);

 

(Integer)를 붙여줘야 정확히 해당 노드를 삭제해준다. 만약에 붙이지 않는다면, v번째 노드를 삭제하라는 말과 같으므로 인덱스 에러가 발생한다. 그러므로 해당 노드를 삭제하고 싶을 땐 꼭 형변환 해주자! 

 

유니온 파인드로도 풀이가 가능하다.