[프로그래머스/JAVA] 가장 먼 노드(DFS/BFS)

가장 먼 노드는 5, 4, 6 세 가지 이다.

가장 먼 노드 문제는 노드로 주어지는 상황속에서 1부터 n까지의 관계 안에 가장 먼 노드를 찾는 문제이다. 즉, 위와 같은 모형이 주어지면 가장 먼노드인 5, 4, 6 의 개수 3을 return하면 된다.

우선 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 둘 중 어느 방식을 선택할 것인가에 대해 생각이 필요해보였다. 가장 먼 노드를 따져본다고 했을 때 가정을 해보았다. 그랬더니 순서가 대충 이렇게 나올 것 같다.

1 - 2 - 5(return) - 4 - 3(?) - 6 ...

어떻게 순서를 잡냐에 따라 다르겠지만 4에서 3으로 가는게 말이 될까? 2에서 이웃한 노드도 사실 상 3, 4, 5이기 때문에 2 - 3으로의 순서도 고려해볼 필요가 있다. 깊이 우선 탐색에서는 가장 먼 노드가 몇개있는지 체크하는 부분에서는 어려워보인다. 그러면 이제부터 코딩으로 말고, 우리가 인간적으로 보았을 때 어떻게 가장 먼 노드를 체크하는지 확인해보자.

단순히 보면, 1은 deep이 1단계 / 2, 3의 deep이 2단계 / 5, 4, 6의 deep이 3단계 와 같은 방식으로 생각하게 된다. 우리는 깊이를 우선적으로 살펴보아야 하는 것이 아닌, 너비로 점점 넓혀가면서 우리가 몇 단계에 속하는지 너비 우선 탐색 기법을 사용해야만 한다. 여기까지 생각의 결과를 나타내는건 어려울 수도 있지만 정확히 정해진 답도 없고 스스로 생각할 수 있는 능력이 중요하다 생각한다. 그저 나는 인간적으로 생각해보고 그것을 코딩으로 나타낸 나만의 방식이라는 것이다.

그러면 너비 우선 탐색을 사용해보자.

void search(Node root) {
	Queue queue= new Queue();
	root.marked = true;
	queue.enqueue(root);
	while(!queue.isEmpty()) {
		Node r = queue.dequeue();
		visit(r);
		foreach(Node n in r.adjacent) {
			if(n.marked == false) {
				n.marked = true;
				queue.enqueue(n);
			}
		}
	}
}

너비 우선 탐색의 코드는 다음과 같다. 재귀 함수가 아닌 queue를 사용하면서 queue에 지속적으로 값을 넣었다가 빼면서 너비 우선 탐색을 사용한다. 여기서 중요한 것은 mark와 visit의 차이이다. 둘의 차이를 먼저 정의하면 이렇다.

mark : 아직 방문하지 않은 상태, 해당 노드의 인접한 노드의 mark를 true로 변환하고, 다른 노드의 영향을 받지 않게끔 한다.
visit : 순수 방문 상태, 그리고 당연히 visit이 true면 해당 노드는 mark도 true일 것이다.

mark의 정의가 조금 어렵다. 그러면 위와 같은 상황에서 mark의 역할이 무엇인지 정확히 짚고 넘어가자.

1번 노드가 들어가고 queue에 2와 3이 들어가게 된다. 2와 3은 방문하지 않은 상태이며 mark만 true로 변환했을 뿐이다.
while문에 의해 2번 노드로 진행하게 되고 2의 인접 노드는 3, 4, 5이다. 하지만 3은 mark가 true인 상태이기 때문에 가지 않는다. 즉 4, 5의 노드에만 접근한다. 만약 여기서 2가 3까지 집어 넣게 된다면 queue의 데이터 상태는 다음과 같을 것이다.

첫 번째 while에 의해 2, 3이 들어간다. (현재 노드 1) -> queue : 2 3
두 번째 while에 의해 3, 4, 5가 들어간다. (현재 노드 2) -> queue : 3 3 4 5

3이 두번 체크되기 때문에 이렇게 되어서는 안 된다. 그렇다고 방문한 것도 아닌데 애매해지는 상황이 발생하기에 mark로 나중에 갈 곳이니 지금 가지 말 것이라고 체크하는 것과 같다.

이와 같이 mark와 visit을 사용하며 너비 우선 탐색 기법을 사용하게 된다. 그러면 이제 내가 코딩한 방법을 보여주겠다.

문제 해법

import java.util.*;
class Solution {
    static int count = 0;
    static int answer = 0;

    public int solution(int n, int[][] edge) {
        List<Node> nodeList = new ArrayList<Node>();
        Node root = null;
        for(int i = 1; i <= edge.length; i++) {
            Node node = new Node(i);
            if(i == 1) root = node;
            nodeList.add(node);
        }
        for(int i = 0; i < edge.length; i++) {
            Node node1 = nodeList.get(edge[i][0] - 1);
            Node node2 = nodeList.get(edge[i][1] - 1);
            node1.setNode(node2);
            node2.setNode(node1);
        }
        
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);

        int level = 1;
        root.level = level;
        while(!q.isEmpty()) {
            Node r = q.poll();
            r.mark = true;
            r.state = true;
            for(Node rr : r.adjacent) {
                if(rr.state == false && rr.mark == false) {
                    rr.mark = true;
                    rr.level = r.level + 1;
                    q.add(rr);
                }
            }
        }
        int max = 0;
        for(int i = 0; i < nodeList.size(); i++) {
            int l = nodeList.get(i).level;
            if(max < l) {
                max = l;
                answer = 1;
            } else if(max == l){
                answer++;
            }
        }
        return answer;
    }
}

class Node {
    List<Node> adjacent;
    int data;
    int level;
    boolean state;
    boolean mark;

    Node(int data) {
        this.data = data;
        level = 0;
        adjacent = new ArrayList<Node>();
    }
 
    public void setNode(Node n) {
        adjacent.add(n);
    }
}

 

가장 아래 있는 Node클래스를 먼저 설명하겠다.
Node는 총 5가지의 변수를 가지고 있으며 adjacent는 인접한 노드, data는 현재 노드의 데이터 값, level은 현재 깊이, state는 방문 여부, mark는 마크와 같다. level는 값을 queue에 넣기 전에 자신 노드의 레벨을 체크하고 +1한 값을 다음에 갈 노드의 level에 넣는 방식으로 진행하였다.

다음으로는 초기화 방법이다.
root는 처음 1이 들어갈 때의 노드 값으로 초기화하며, 이후 배열로 주어지는 노드 연결선을 이어주기 위해 for구문으로 각 adjacent 변수에 넣어준다.

        List<Node> nodeList = new ArrayList<Node>();
        Node root = null;
        for(int i = 1; i <= edge.length; i++) {
            Node node = new Node(i);
            if(i == 1) root = node;
            nodeList.add(node);
        }
        for(int i = 0; i < edge.length; i++) {
            Node node1 = nodeList.get(edge[i][0] - 1);
            Node node2 = nodeList.get(edge[i][1] - 1);
            node1.setNode(node2);
            node2.setNode(node1);
        }

 

다음으로는 너비 우선 탐색에 들어가기 전에 root 값을 queue에 값에 넣고, state를 true시킨다. 다음 해당 노드의 인접한 노드들을 탐색하고, 그 노드가 방문도 하지 않은, 마크처리도 되어 있지 않은 상태라면 그 노드의 mark를 true로 변환시키고, level값 또한 하나 증가시킨다. 후에 queue에 노드를 추가시켜 while문에 의해 반복될 때 한번 더 추출할 수 있도록 한다.

가장 핵심적인 부분이다.

        Queue<Node> q = new LinkedList<Node>();
        q.add(root);

        int level = 1;
        root.level = level;
        while(!q.isEmpty()) {
            Node r = q.poll();
            r.state = true;
            for(Node rr : r.adjacent) {
                if(rr.state == false && rr.mark == false) {
                    rr.mark = true;
                    rr.level = r.level + 1;
                    q.add(rr);
                }
            }
        }

 

max를 0으로 초기화 시키고 node의 level을 지속적으로 확인하면서 현재까지 나온 max의 값이 최대치인지 확인하고 max가 바뀌게 된다면 answer을 1로 초기화. 만약에 max값과 현재 level과 같다면 가장 깊은 노드가 하나 더 있다는 것이므로 +1을 해줌으로써 결과를 나타내게 된다.

        int max = 0;
        for(int i = 0; i < nodeList.size(); i++) {
            int l = nodeList.get(i).level;
            if(max < l) {
                max = l;
                answer = 1;
            } else if(max == l){
                answer++;
            }
        }
        return answer;