고도고도
🍎🍏
고도고도
전체 방문자
7,922
오늘
2
어제
26
  • 분류 전체보기 (149) N
    • 🔨 프로젝트 (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • 💻 개발 (43) N
      • TIL (16)
      • Android (6)
      • Kotlin (4)
      • Flutter (9) N
      • Node.js (5)
      • Error (3) N
    • ✏️ 알고리즘 (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • ✍️ 코테 준비 (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • 📚 CS (6)
      • Operating System (6)
    • ⛹️ 라이프 (50)
      • 2020 겨울방학 모칵코(팀) (13)
      • 2020 겨울방학 모각코(개인) (13)
      • 2021 여름방학 모칵코(팀) (8)
      • 2021 여름방학 모각코(개인) (7)
      • 코딩 테스트 (1)
      • 회고 (7)

블로그 메뉴

  • 홈
  • 깃허브
  • 링크드인

인기 글

  • [TIL] 22.03.13
    2022.03.13
    [TIL] 22.03.13
  • [문자열 / Kotlin] 2020 KAKAO⋯
    2022.03.11
    [문자열 / Kotlin] 2020 KAKAO⋯
  • [TIL] 22.03.20
    2022.03.20
    [TIL] 22.03.20
  • [퍼듀 일기] 어느덧 한 달째
    2022.03.01
    [퍼듀 일기] 어느덧 한 달째
  • [퍼듀 일기] 적응 완료
    2022.03.05
    [퍼듀 일기] 적응 완료

최근 글

  • [Flutter] ModalBottomSheet가⋯
    2022.08.09
    [Flutter] ModalBottomSheet가⋯
  • [Error / Gradle] The current⋯
    2022.08.09
    [Error / Gradle] The current⋯
  • [Flutter / Dart] What is Equa⋯
    2022.08.06
    [Flutter / Dart] What is Equa⋯
  • [Flutter] BLoC 패턴으로 자동⋯
    2022.07.26
    [Flutter] BLoC 패턴으로 자동⋯
  • [Flutter / Dart] What is Sing⋯
    2022.07.21
    [Flutter / Dart] What is Sing⋯

최근 댓글

  • 잘보고 갑니다~
    개갓세
  • 좋은 글이네요
    날인로세
  • 잘 보고 갑니다^^
    프로퍼티
hELLO · Designed By 정상우.
고도고도

🍎🍏

[DFS와 BFS] [Python / C++] 1707. 이분 그래프
✍️ 코테 준비/DFS, BFS

[DFS와 BFS] [Python / C++] 1707. 이분 그래프

2021. 4. 14. 14:45

www.acmicpc.net/problem/1707

 

1707번: 이분 그래프

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수

www.acmicpc.net

 

 

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.


우선 이 문제를 풀기 전에 이분 그래프의 대한 의미를 집고 넘어가야겠다.

출처 : https://gmlwjd9405.github.io

 

이분 그래프는 위의 그림처럼 인접한 노드를 다른 색으로 칠했을 때 두 가지 색으로 표현 가능한 그래프를 말한다.

 

대충 감이 오지 않는가?

 

본인은 BFS를 활용하여 문제를 해결하였고 DFS로도 해결 가능할 것으로 보인다.

 

해결 방법

간선 정보를 저장할 배열과 방문 여부를 저장할 배열, 두 개를 선언한다.

양방향 탐색이 필요하므로 간선 정보를 저장할 때 양방향으로 저장해준다.

이후 BFS를 통해 탐색을 진행하는데 인접한 노드를 방문하면 현재 노드와 다른 색(?)으로 칠해주는 것이 핵심이다.

 

1. 현재 노드를 1로 설정하고 인접한 노드가 방문하지 않은 경우 인접한 노드를 -1로 설정한다.

(1 : RED, -1 : BLUE라고 생각하면 이해하기 쉬울 것이다.)

 

2. 이미 방문한 노드인 경우 현재 노드와 인접한 노드의 합을 구해서 0이 아닌 경우는 이는 이분 그래프가 아니라는 것을 나타낸다.

(ex 현재 노드의 색 = 1, 인접한 노드의 색 = 1 -> 합하면 2 -> 이분 그래프가 아님.)

 

3. 모든 노드에 대해 위 과정을 반복한다.

 

코드로 나타내면 아래와 같다.

 

 

이렇게 하고 실행을 돌렸는데

???

 

구현 방법은 문제가 없어보였다. 결국 반례를 찾지 못하고 질문 게시판을 참고했더니 적절한 반례가 있었다.

나는 문제를 해결할 때 모든 간선이 연결되어 있다고 생각하였고 BFS를 한 번만 탐색하도록 코드를 구현했었다.

하지만 아래 그림과 같은 그래프도 결국 이분 그래프가 될 수 있다는 것을 인지하지 못했다.

 

적절한 반례

 

이후 그래프가 나눠진 경우에도 탐색을 할 수 있도록 코드를 추가하였고 해결할 수 있었다.

 

파이썬으로 구현한 코드이다.

주석 처리한 부분이 위에서 말한 반례도 통과할 수 있도록 추가한 코드이다.

 

 

C++로 구현한 코드이다.

 

 

언어 2개 정도는 능숙하게 써야한다고 생각해서 C++로도 구현하고 있는데 확실히 파이썬이 쉬운 것 같다.

"문제 읽고 파이썬으로 해결하는 시간  =<  C++로 다시 구현하는 시간"  약간 이렇다...

저작자표시

'✍️ 코테 준비 > DFS, BFS' 카테고리의 다른 글

[BFS][Kotlin] 2021 카카오 채용연계형 인턴십 - 거리두기 확인하기  (0) 2022.03.20
[DFS와 BFS] [Python / C++] 1260. DFS와 BFS  (0) 2021.04.18
[DFS와 BFS] [Python / C++] 1707. 이분 그래프  (0) 2021.04.14
[DFS와 BFS] [Python / C++] 7562. 나이트의 이동.  (0) 2021.04.13
[DFS와 BFS] [Python / C++] 2206. 벽 부수고 이동하기.  (0) 2021.04.12
    '✍️ 코테 준비/DFS, BFS' 카테고리의 다른 글
    • [BFS][Kotlin] 2021 카카오 채용연계형 인턴십 - 거리두기 확인하기
    • [DFS와 BFS] [Python / C++] 1260. DFS와 BFS
    • [DFS와 BFS] [Python / C++] 7562. 나이트의 이동.
    • [DFS와 BFS] [Python / C++] 2206. 벽 부수고 이동하기.
    C++, dfs와 bfs, 백준, 파이썬
    고도고도
    고도고도
    좋아하는 것을 하자\n 스위프트 찍먹중\n 광고 없는 블로그
    댓글쓰기
    다음 글
    [DFS와 BFS] [Python / C++] 1260. DFS와 BFS
    이전 글
    [DFS와 BFS] [Python / C++] 7562. 나이트의 이동.
    • 이전
    • 1
    • 2
    • 3
    • 4
    • 5
    • 다음