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

2022년 04월 29일 금요일 - 와 오늘 다 잃음....

오늘 올려볼 문제는 785 Is Graph Bipartite? 이라는 문제이다.

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

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

처음 보는 개념이어뜸

입력

사진에서도 볼 수 있듯이 2차원 배열 1개가 들어온다.

---

풀이 및 코드

이분 그래프인지 판단하는 문제다.

오늘은 시행착오를 겪었다.

이분그래프가 뭔지 몰라서 검색해봤는데 판단하는 방법이 나와있어서 조금 참고해서 풀었다.

bsf를 하면서 노드에 색깔을 저장하는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean isBipartite(int[][] graph) {
        Queue<Integer> q = new  LinkedList<>();
        HashMap<Integer, Character> map = new HashMap<>();

        for(int a = 0; a < graph.length; a++)
        {
            if(!map.containsKey(a))
            {
                q.add(a);

                char color = 'b';

                while(!q.isEmpty())
                {
                    int size = q.size();

                    color = color == 'b' ? 'r' : 'b';

                    for(int i = 0; i < size; i++)
                    {
                        int now = q.poll();

                        if(map.containsKey(now)) continue;

                        map.put(now, color);

                        for(int num : graph[now])
                        {
                            if(map.getOrDefault(num, 'n') != 'n')
                            {
                                if(map.get(num) == color) return false;
                            }
                            else
                            {
                                q.add(num);
                            }
                        }
                    }
                }
            }
        }

        return true;
    }
}

---

제출 화면

오늘은 문제가 생각보다 어려웠다.

내일은 깔삼하게 잘 풀 수 있었으면 좋겠다.

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