TIL_20230519

오늘 할 일

• LeetCode 데일리 문제 풀기
• 영화보기

오늘 배운 것

LeetCode 데일리 문제 풀기

• 오늘의 문제: Is Graph Bipartite?(https://leetcode.com/problems/is-graph-bipartite/)
• 난이도: medium
• 문제 조건
  
  • n개의 노드를 가진 무방향 그래프가 주어지고, 각 노드는 0부터 n - 1까지의 번호가 매겨져있다. 2차원 배열 graph를 받고, graph[u]는 노드 u가 인접해있는 노드의 배열이다. 더 일반적으로, graph[u]에 포함된 각 v는 노드 u와 노드 v 사이에 방향이 없는 간선을 가진다. 그 그래프는 다음과 같은 내용을 따른다.
    • 자기 자신으로 가는 간선이 없다. (graph[u]에는 u가 포함되지 않는다.)
    • 병렬 간선이 없다. (graph[u]는 중복된 값이 포함되지 않는다.)
    • 만약 graph[u] 내에 v가 있다면 u는 graph[v]에 있다. (그래프가 무방향이다.)
    • 그래프는 연결되지 않을 수도 있고, 두 개의 노드 u와 v 사이에 경로가 없을 수 있다는 의미이다.
  • 그래프의 모든 간선이 집합 A의 노드와 집합 B의 노드를 연결하도록 노드를 두 개의 독립적인 집합 A와 B로 분할할 수 있는 경우 그래프는 bipartite된다.
  • 만약 bipartite라면 true를 반환해라.
• 문제 해결 과정
  
  • 시간복잡도는 O(v + e)이다. 정점과 간선의 수만큼만 고려하면 된다.
  • 각 정점을 방문하면서 그룹을 나눠줘야 한다.
  • dfs/bfs 사용.
  • 정점을 두 그룹으로 나눌 때, 한 정점에 인접한 정점들은 다른 그룹에 속해야 한다.
  • dfs를 순회하면서 방문한 정점을 visited에 표시해주는데, group을 1과 -1로 나눠 visited에 저장한다. 만약 인접해있는 group의 visited 값이 현재 정점의 group과 같다면 인접한 정점이 같은 그룹이면 안되는 규칙을 위반하므로 false이다.
  • 또한 아직 방문하지 않은 인접한 정점이면 다른 그룹인지 확인해본다. 이 때, dfs의 결과가 false이면 false를 반환한다.
  • dfs를 마치고 나서도 false가 반환되지 않은 상태면 true이다.

영화보기

• 오늘은 영화를 봤습니다. - 가디언즈 오브 갤럭시 3
• 마블 영화가 점점 이상해지고 있다는 생각을 하던 요즘, 가오갤3를 보면서 간만에 순수한 즐거움을 느꼈습니다.
• 가오갤 짱!

느낀점

• dfs/bfs 문제가 나오면 왜이리 어려운지 모르겠습니다... 언제쯤 잘할 수 있을까요,,,
• 오늘은 특별한 일이 있어서 영화를 보고 휴식하는 하루였습니다.
• 그래도 리트코드 풀었습니다!

내일 할 일

• LeetCode 데일리 문제 풀기
• Heart - 게시판 글 수정 및 삭제 이미지 처리 로직 코드 작성하기(자유게시판)