[LeetCode] 133번 문제를 풀어보았다. (ft. java)

2022년 2월 23일 수요일 - 오늘 너무 졸린데...

오늘 올려볼 문제는 133번 Clone Graph 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

오늘 문제는 꽤 귀찮았는데 안귀찮게 푸는 방법이 이써따...

입력

사진에서도 볼 수 있듯이 그래프의 시작 노드 하나가 입력으로 들어온다.

---

풀이 및 코드

주어진 그래프를 그대로 복사하여 리턴하는 문제다.

오늘은 처음부터 정답을 생각해냈다.

주어진 그래프를 순회하는 대로 그래프를 만드는 것이다.

이 때 계속 new를 사용하면 제대로 된 복사가 되지 않으므로 val를 기준으로 노드를 저장하고 있다가 연결해주는 방식으로 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    Node result;
    Queue<Node> q = new LinkedList<Node>();

    Node[] nodes = new Node[105];
    boolean[] visit = new boolean[105];

    public Node cloneGraph(Node node) {
        if(node == null)
            return null;

        if(node.neighbors.size() == 0)
            return new Node(node.val);

        result = new Node(node.val);
        nodes[result.val] = result;

        dfs(node);

        return result;
    }

    public void dfs(Node root)
    {
        if(visit[root.val])
            return;

        visit[root.val] = true;

        Node temp;
        for(int i = 0; i < root.neighbors.size(); i++)
        {
            temp = result;

            if(nodes[root.neighbors.get(i).val] == null)
                nodes[root.neighbors.get(i).val] = new Node(root.neighbors.get(i).val);
            result.neighbors.add(nodes[root.neighbors.get(i).val]);
            result = result.neighbors.get(i);
            dfs(root.neighbors.get(i));

            result = temp;
        }
    }
}

---

제출 화면

오늘은 문제가 귀찮았다.

하지만 귀찮지 않게 푸는 방법이 있었던 것을 보면 뭔가 귀찮다 싶으면 짧게 풀 수도 있겠구나 생각을 해야겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.