Is Graph Bipartite? - LeetCode
접근 방법 [필수 작성]
제한 조건 확인
- 그래프가 none 일수도 있음
- 최대 99*99 까지 있을 수 있음
1차 아이디어
이분그래프 만들 수 있는지 없는지 묻는 문제
BFS 로 이전노드가 검정이면 다음노드는 하얀색으로 칠하기
만약 이미 방문한 노드를 만났는데 그 노드가 현재 노드랑 색깔이 똑같으면 False
모든 경우를 다 탐색했는데 그런 경우가 없으면 True 반환
현재 BFS 탐색의 깊이를 누적으로 기록하여 홀짝으로 나누어
짝수면 빨강
홀수면 파랑으로 정의
흰색이면 아직 방문 안한 노드
for 문으로 모든 노드 탐색 → 여기 포문으로 구현하면 안되고 queue 로 구현해야됨
for 문으로 모든 다음 노드의 색깔을 확인 후
흰색이면
현재깊이가 짝수면 빨강으로 업데이트
현재깊이가 홀수면 파랑으로 업데이트
흰색이 아니면
다음 노드의 색깔과 현재노드의 색깔이 같으면
pass
다르면
return False
예외케이스는
외딴섬 그래프가 존재하는 경우
2차 아이디어
1차 아이디어 너무 조잡하고 고칠게 많아서 아예 갈아엎고 다시 새로 아이디어 짰음
아이디어는 그냥 그래프에 사람이 depth가 하나씩 증가하는 방향으로 BFS 형식으로 색깔을 칠해넣는 방법에 착안하였음.
색깔을 칠하면서, 다음 곳이 같은 색인지 아닌지 검증함.
외딴 섬 그래프가 있을 수도 있기 때문에
BFS 로 서치하되, queue 에 있는 모든거 다 서치했는데 여전히
color_matrix에 “W” 가 존재하면 해당 인덱스 노드를 다시 시작점으로 잡고 계속 BFS 해주었음
큐에 저장할때는 [현재노드인덱스,다음노드인덱스리스트] 형식으로 저장해주어서 넘겨주었음.
큐에 넣은 다음노드를 기준으로 다음노드가 W 이면,
현재노드와 다른 색을 칠해주고
W가 아니면
현재노드와 색깔을 비교해서
색깔이 같으면 False 리턴
색깔이 다르면 pass
시간복잡도
99개의 노드에 대해서 각 노드는 자신이랑 인접한 노드가 자기랑 같은 색깔인지 확인하기 위해 최대 99번 탐색
따라서 99*99 로 풀 수 있음
자료구조
queue 를 활용한 BFS 구현
코드 구현 [필수 작성]
1차시도 → 바로 통과 (100/100)
#2시30분 시작 -> 3시30분 끝
from collections import deque
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
n = len(graph)
color_matrix = ["W" for _ in range(n)]
def opposite_color(color):
if color == "R":
return "B"
elif color == "B":
return "R"
while "W" in color_matrix:
curr_node_idx = color_matrix.index("W")
queue = deque([])
queue.append([curr_node_idx,graph[curr_node_idx]])
color_matrix[curr_node_idx] = "R"
while queue:
curr_node_idx,next_node_idx_list = queue.popleft()
for next_node_idx in next_node_idx_list:
if color_matrix[next_node_idx] == "W":
color_matrix[next_node_idx] = opposite_color(color_matrix[curr_node_idx])
queue.append([next_node_idx,graph[next_node_idx]])
else:
if color_matrix[curr_node_idx] == color_matrix[next_node_idx]:
return False
else:
pass
#queue.append([next_node_idx,graph[next_node_idx]])
#색깔을 칠할때 어차피 이분그래프인지 검증을 하기 때문에 또 queue에 append 안해줘도 될것같다.
return True
[해설코드]
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
color = [-1 for _ in range(len(graph))]
for i, c in enumerate(color):
if c == -1:
queue = deque([i])
color[i] = 0
while queue:
cur_v = queue.popleft()
for next_v in graph[cur_v]:
if color[next_v] == -1:
color[next_v] = color[cur_v] ^ 1
queue.append(next_v)
elif color[next_v] == color[cur_v]:
return False
return True배우게 된 점 [ 필수 X ]
비트연산자를 활용한 이분그래프 색칠하기 구현
color[next_v] = color[cur_v] ^ 1
질문 [ 필수 X ]
자유 형식
피드백 [ 코치 작성 ]
수고하셨습니다!
