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

2023년 05월 19일 금요일 - 너무 오랜만에 쓰는구만?

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

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

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

으어 이번주 너무 길어

입력

사진에서도 볼 수 있듯이 그래프 1개가 입력으로 들어온다.

---

풀이 및 코드

입력으로 들어온 그래프가 Bipartite인지 판단하는 문제다.

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

BFS로 level단위를 돌면서 컬러링을 진행하는 식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean isBipartite(int[][] graph) {
        var arr = new Boolean[graph.length];
        var visit = new boolean[graph.length];
        var q = new LinkedList<Integer>();
        
        for(int i = 0; i < graph.length; i++) {
            if(arr[i] != null) continue;
            q.add(i);
            arr[i] = true;
            
            while(!q.isEmpty()) {
                var now = q.poll();

                if(visit[now]) continue;

                visit[now] = true;

                for(var child: graph[now]) {
                    if(arr[child] == null) arr[child] = !arr[now];
                    else if(arr[child] == arr[now]) return false;

                    q.add(child);
                }
            }
        }
        
        return true;
    }
}

---

제출 화면

요즘 자꾸 블로그 쓰는걸 까먹어서 오랜만에 올려본다!

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