[백준] 1707번 이분 그래프 _ Python

2024. 4. 10. 16:32·Algorithms/Graph
목차
  1. 1. Preview
  2. 2. 초기 접근 방법
  3. 3. 생각
  4. 4. 코드

https://www.acmicpc.net/problem/1707

 

1707번: 이분 그래프

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에

www.acmicpc.net

 

 


 

1. Preview

시간 복잡도: O(V+E)

 

공간 복잡도: O(V or E)

 

참고 : https://ji-gwang.tistory.com/293

 

유형: dfs, bfs

 

 


 

2. 초기 접근 방법

이분 그래프

: 인접한 정점끼리 서로 다른색으로 칠해서 모든 정점을 2가지 색으로만 칠할 수 있는 그래프

 

https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

 

 

2개의 집합을 두고, 인접 노드를 번갈아 저장하는 이상한 방식으로 문제를 접근해 관련 내용 정리는 생략하였다;;

 

 


 

3. 생각

1) dfs

dfs 탐색을 진행하면서 인접 노드 색깔을 계속 바꿔준다.

이 때 인접 노드와 색깔이 같으면 False를 반환한다.

def dfs(start, idx):
    for k in graph[start]:
        # 인접 노드는 다른 "표식"
        if not visited[k]:
            visited[k] = -idx
            judge = dfs(k, -idx)

            # dfs 탐색 중에 인접 노드와 같은 "표식"이 있다면
            if not judge:
                return False

        # 인접 노드와 같은 "표식"이라면
        if visited[k] == visited[start]:
            return False

    return True

 

 

2) bfs

마찬가지로 bfs 탐색을 진행하면서 인접 노드 색깔을 계속 바꿔준다.

이 때 인접 노드와 색깔이 같으면 False를 반환한다.

def bfs(start):
    q = deque()
    q.append((start, 1))
    visited[start] = 1

    while q:
        node, idx = q.popleft()

        for k in graph[node]:
            # 인접 노드는 다른 "표식"
            if not visited[k]:
                visited[k] = -idx 
                q.append((k, -idx))

            # 인접 노드와 같은 "표식"이라면
            if visited[k] == visited[node]:
                return False

    return True

 

 


 

4. 코드

 

import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def dfs(start, idx):
    for k in graph[start]:
        # 인접 노드는 다른 "표식"
        if not visited[k]:
            visited[k] = -idx
            judge = dfs(k, -idx)

            # dfs 탐색 중에 인접 노드와 같은 "표식"이 있다면
            if not judge:
                return False

        # 인접 노드와 같은 "표식"이라면
        if visited[k] == visited[start]:
            return False

    return True


def bfs(start):
    q = deque()
    q.append((start, 1))
    visited[start] = 1

    while q:
        node, idx = q.popleft()

        for k in graph[node]:
            if not visited[k]:
                visited[k] = -idx # 인접 노드는 다른 "표식"
                q.append((k, -idx))

            # 인접 노드와 같은 "표식"이라면
            if visited[k] == visited[node]:
                return False

    return True


T = int(input())
for _ in range(T):
    V, E = map(int, input().split())

    graph = [[] for _ in range(V+1)]
    visited = [0 for _ in range(V+1)]

    for _ in range(E):
        s, e = map(int, input().split())
        graph[s].append(e) # 양방향 연결
        graph[e].append(s)

    for i in range(1, V):
        if not visited[i]:
            result = dfs(i, 1)
            if not result:
                break

    if result:
        print("YES")
    else:
        print("NO")
저작자표시 (새창열림)

'Algorithm > Graph' 카테고리의 다른 글

[백준] 2206번 벽 부수고 이동하기 _ Python  (0) 2024.04.09
[백준] 9466번 텀 프로젝트 _ Python  (0) 2024.03.20
[백준] 16928번 뱀과 사다리 게임 _ Python  (0) 2024.03.17
[백준] 16624번 피리 부는 사나이 _ Python  (0) 2024.03.10
[백준] 11559번 Puyo Puyo _ Python  (0) 2024.02.01
  1. 1. Preview
  2. 2. 초기 접근 방법
  3. 3. 생각
  4. 4. 코드
'Algorithms/Graph' 카테고리의 다른 글
  • [백준] 2206번 벽 부수고 이동하기 _ Python
  • [백준] 9466번 텀 프로젝트 _ Python
  • [백준] 16928번 뱀과 사다리 게임 _ Python
  • [백준] 16624번 피리 부는 사나이 _ Python
wch_t
wch_t
  • wch_t
    끄적끄적(TIL)
    wch_t
  • 글쓰기 관리
  • 전체
    오늘
    어제
    • 분류 전체보기 (171)
      • Architecture (0)
      • Algorithm (67)
        • Math (5)
        • Simulation (1)
        • Data Structure (4)
        • DP (7)
        • Brute Fource (10)
        • Binary Search (6)
        • Greedy (2)
        • Graph (11)
        • Mst (1)
        • Shortest path (10)
        • Two Pointer (1)
        • Tsp (3)
        • Union Find (2)
        • Mitm (1)
      • CS (2)
        • 데이터베이스 (5)
        • 네트워크 (5)
      • DB (6)
      • DevOps (17)
        • AWS (9)
        • Docker (1)
        • CI-CD (5)
      • Error (1)
      • Project (0)
        • kotrip (0)
      • Spring (59)
        • 끄적끄적 (5)
        • 기본 (9)
        • MVC 1 (7)
        • MVC 2 (11)
        • ORM (8)
        • JPA 1 (7)
        • JPA 2 (5)
        • Spring Data Jpa (7)
      • Test (2)
      • TIL (6)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    view algorithm
    Merge
    spring-cloud-starter-bootstrap
    백준 17299 파이썬
    애플
    Sxssf
    aws secrets manager
    Jenkins
    백준 17289 파이썬
    docker: not found
    TempTable
    scope
    백준 3015 파이썬
    docker
    spring-cloud-starter-aws-secrets-manager-config
    form_post
    apache poi
    response_mode
  • 최근 댓글

  • hELLO· Designed By정상우.v4.10.3
wch_t
[백준] 1707번 이분 그래프 _ Python
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.