기본 개념에 충실하게 배우기 위한 기초적인 DFS 문제를 풀어보았다. n만큼의 컴퓨터들이 존재하고 이 네트워크들이 서로 연결이 되있다고 했을때 가장 최소한의 선을 움직여서 모든 네트워크가 연결이 될수있게 하면 되는 문제이다. 혹시라도 그것이 불가능하다면 -1을 리턴.
처음에 이 문제를 봤을때는 분명히 풀어본 문제라는걸 알지만서도 헷갈렸다. 어떻게 선의 개수를 알면 좋을지 등등. 그래도 머리속에 남아있는 기억을 바탕으로 천천히 풀어보았다. 가장 먼저 -1을 리턴하는 조건부터 생각했을때 만약에 연결되 있는 선의 개수가 n만큼의 컴퓨터를 연결하는 수보다 적다면 어떤 짓을해도 불가능하기 때문에 그 조건을 앞세워서 -1을 리턴하게 했다.
그리고 각 컴퓨터가 필수적으로 연결이 한번씩 되야한다는 이유를 알고 있기때문에 연결된 각 컴퓨터의 동선을 따라가고 처음 연결되는 컴퓨터가 있다면 answer 값을 감소시켜줬다 (answer 값은 n-1로 시작). 만약에 하나의 컴퓨터가 연속적으로 연결이 된다면 그것은 중복이므로 넘어갔고 마지막까지 남는 answer 값이 즉 최소한으로 모든 컴퓨터를 연결할수있는 숫자가 되는것이다.
항상 0번째 컴퓨터부터 시작하라는 소리는 없었기 때문에 모든 노드를 상대로 traverse 해주었다. 이 코드를 안썼다면 아마 끝에 테스트케이스에서 오류가 났었을것이다... 이 문제를 풀수있는 또다른 방법으로는 Union Find 방식이 있는데 솔직히 좀 귀찮아서 안했다. 그래도 약식으로 나마 설명하자면 각 컴퓨터를 해당 부모에 맞게 연결 시켜주고 만약에 컴퓨터 사이에 해당 노드가 같다면 answer-- 해주면 똑같은 답이 나왔을것이다. Union Find 를 이용한 문제는 내 블로그 태그에 적혀있은 확인하면 좋을거같다.
배운점:
1. DFS 를 활용할때 꼭 써야하는 visited 벡터.
2. 문제에 맞는 DFS활용.
