이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 51 번째 글 입니다.

  • Part 1 - 백준(1003번): 피보나치 함수
  • Part 2 - 백준(1010번): 다리놓기
  • Part 3 - 백준(1012번): 유기농 배추
  • Part 4 - 백준(10159번): 저울
  • Part 5 - 백준(10164번): 격자상의 경로
  • Part 6 - 백준(1018번): 체스판 다시 칠하기
  • Part 7 - 백준(1018번): 체스판 다시 칠하기
  • Part 8 - 백준(1022번): 소용돌이 예쁘게 출력하기
  • Part 9 - 백준(10775번): 공항
  • Part 10 - 백준(10816번): 숫자 카드2
  • Part 11 - 백준(10816번): 숫자카드 2
  • Part 12 - 백준(10819번): 차이를 최대로
  • Part 13 - 백준(10830번): 행렬 곱셈
  • Part 14 - 백준(10844번): 쉬운 계단수
  • Part 15 - 백준(10868번): 최소값
  • Part 16 - 백준(1092번): 배
  • Part 17 - 백준(11003번): 최솟값 찾기
  • Part 18 - 백준(1102번): 발전소
  • Part 19 - 백준(11048번): 이동하기
  • Part 20 - 백준(11053번): 가장 긴 증가하는 부분 수열
  • Part 21 - 백준(11054번): 가장 긴 바이토닉 부분 수열
  • Part 22 - 백준(11055번): 가장 긴 증가하는 부분 수열2
  • Part 23 - 백준(11057번): 오르막 수
  • Part 24 - 백준(1120번): 문자열
  • Part 25 - 백준(11403번): 경로 찾기
  • Part 26 - 백준(11404번): 플루이드
  • Part 27 - 백준(1149번): RGB 거리
  • Part 28 - 백준(11559번): puyo puyo
  • Part 29 - 백준(11655번): ROT13
  • Part 30 - 백준(1167번): 트리의 지름
  • Part 31 - 백준(11722번): 가장 감소하는 부분 수열
  • Part 32 - 백준(12015번): 가장 긴 증가하는 부분 수열(LIS) 2
  • Part 33 - 백준(12851번): 숨바꼭질2
  • Part 34 - 백준(12852번): 1로 만들기 2
  • Part 35 - 백준(12865번): 평범한 배낭
  • Part 36 - 백준(1300번): K번째 수
  • Part 37 - 백준(1325번): 효율적인 해킹
  • Part 38 - 백준(13549번): 숨바꼭질3
  • Part 39 - 백준(13913번): 숨바꼭질4
  • Part 40 - 백준(14002번): 가장 긴 증가하는 부분 수열 4
  • Part 41 - 백준(1431번): 시리얼 넘버
  • Part 42 - 백준(1436번): 영화감독 숌
  • Part 43 - 백준(14499번): 주사위 굴리기
  • Part 44 - 백준(14888번): 연산자 끼워넣기
  • Part 45 - 백준(14889번): 스타트와 링크
  • Part 46 - 백준(14891번): 톱니바퀴
  • Part 47 - 백준(15658번): 연산자 끼워넣기 2
  • Part 48 - 백준(15686번): 치킨 배달
  • Part 49 - 백준(1697번): 숨바꼭질
  • Part 50 - 백준(1697번): 숨바꼭질
  • Part 51 - This Post
  • Part 52 - 백준(1708번): 볼록 껍질
  • Part 53 - 백준(17136번): 색종이 붙이기
  • Part 54 - 백준(1717번): 집합의 표현
  • Part 55 - 백준(17298번): 오큰수
  • Part 56 - 백준(17626번): Four Squares
  • Part 57 - 백준(18870번): 좌표 압축
  • Part 58 - 백준(1890번): 점프
  • Part 59 - 백준(1918번): 후위 표기식
  • Part 60 - 백준(1929번): 소수 구하기
  • Part 61 - 백준(1963번): 소수 경로
  • Part 62 - 백준(1965번): 상자넣기
  • Part 63 - 백준(1976번): 여행가자
  • Part 64 - 백준(1987번): 알파벳
  • Part 65 - 백준(1992번): 쿼드트리
  • Part 66 - 백준(2003번): 수들의 합2
  • Part 67 - 백준(20040번): 사이클 게임
  • Part 68 - 백준(2042번): 구간 합 구하기
  • Part 69 - 백준(2108번): 통계학
  • Part 70 - 백준(2110번): 공유기 설치
  • Part 71 - 백준(2156번): 포도주 시식
  • Part 72 - 백준(2193번): 이친수
  • Part 73 - 백준(2231번): 분해합
  • Part 74 - 백준(2250번): 트리의 높이와 너비
  • Part 75 - 백준(2293번): 동전 1
  • Part 76 - 백준(2294번): 동전 2
  • Part 77 - 백준(2343번): 기타 레슨
  • Part 78 - 백준(2468번): 안전 영역
  • Part 79 - 백준(2512번): 예산
  • Part 80 - 백준(2529번): 부등호
  • Part 81 - 백준(2565번): 전깃줄
  • Part 82 - 백준(2581번): 소수
  • Part 83 - 백준(2583번): 영역구하기
  • Part 84 - 백준(2630번): 색종이 만들기
  • Part 85 - 백준(2644번): 촌수계산
  • Part 86 - 백준(2667번): 단지번호붙이기
  • Part 87 - 백준(2751번): 수 정렬하기 2
  • Part 88 - 백준(2798번): 블랙잭
  • Part 89 - 백준(2904번): 수학은 너무 쉬워
  • Part 90 - 백준(2986번): 파스칼
  • Part 91 - 백준(3015번): 오아시스 재결합
  • Part 92 - 백준(3190번): 뱀
  • Part 93 - 백준(3190번): 벽 부수고 이동하기
  • Part 94 - 백준(4195번): 친구 네트워크
  • Part 95 - 백준(4948번): 베르트랑 공준
  • Part 96 - 백준(4963번): 섬의 개수
  • Part 97 - 백준(4991번): 로봇 청소기
  • Part 98 - 백준(5373번): 큐빙
  • Part 99 - 백준(5437번): 불
  • Part 100 - 백준(6171번): 땅따먹기
  • Part 101 - 백준(6603번): 로또
  • Part 102 - 백준(6603번): 로또
  • Part 103 - 백준(7562번): 나이트의 이동
  • Part 104 - 백준(7568번): 덩치
  • Part 105 - 백준(7576번): 토마토
  • Part 106 - 백준(7579번): 앱
  • Part 107 - 백준(7785번): 회사에 있는 사람
  • Part 108 - 백준(9012번): 괄호
  • Part 109 - 백준(9020번): 골드바흐의 추측
  • Part 110 - 백준(9184번): 신나는 함수 실행
  • Part 111 - 백준(9251번): LCS
  • Part 112 - 백준(9421번): 소수상근수
  • Part 113 - 프로그래머스: 가장 큰 정사각형 찾기
▼ 목록 보기

목차

▼ 내리기

골드4 : 그래프 문제이다.

생각

이분 그래프란 무엇인가? 문제를 읽고는 파악하는 게 힘들었다. 차라리 그림으로 보는 것이 좋다.

이분 그래프의 모양

왼쪽과 같은 그래프가 있을 이걸 오른쪽 그림처럼 바꿀 수 있느냐의 문제이다. 즉 저는 두 개의 집합으로 나눴을 때, 그 집합 내에 소속되는 정점과 인접하지 않는 (서로소 관계를 유지하는) 그래프 라 할 수 있다. 여기서 핵심은 나와 인접한 노드들의 색이 반대라는 것이다.

풀이

풀이 방법은 생각 보다 간단하다. 물론 처음에는 좀 삽질을 했지만.. 여전히 그래프 문제이기 때문에 탐색 방법론 부터 생각하는 것이 합리적이다.

가장 생각하기 어려운 모양 부터 생각해 보겠다. 아래의 예는 그래프가 발생했을 때, 닫힌 그래프로 구성이 되어 정확하게 3개로 쪼개지는 경우에 대해 생각해 본 것이다.

  1. 닫힌 그래프는 여러개 존재할 수 있다. (그래프 입력 : a, b, c의 닫힌 그래프로 나뉜다고 가정해보자.)
  2. 각각의 닫힌 그래프에서 이분 그래프가 되기 위해서는 나와 인접한 노드의 색이 반대여야 한다. (a 그래프에서 이분 그래프인지 확인한다.)
  3. 이렇게 모든 닫힌 그래프에서 이분 그래프인지 확인했을 때 하나라도 이분 그래프가 아니라면 “No”를 출력한다.
  4. 모든 닫힌 그래프에서 이분 그래프라면, 이 세 닫힌 그래프를 합쳐도 이분 그래프이기 때문에 “YES”를 출력한다.

이번에는 4개의 node에서 2개의 노드만 연결되었을 경우를 생각해 보자. 연결이 되지 않은 노드는 색을 어떻게 칠해주냐에 따라 다르므로, 결국 연결된 그래프에 대해서는 이분 그래프인지를 확인해 주면 된다.

Code

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<queue>

#define MAX 20000
#define RED 1
#define BLUE 2
using namespace std;
vector<int> graph[MAX+1];
int isVisited[MAX+1];
int V, E;

// 내 노드에서 부터 시작해서 연결된 친구들을 다른 색으로 바꾼다.
// 이미 색이 칠해져 있으면 탐색하지 않는다.
void dfs(int voltex, int color){
    isVisited[voltex] = color;
    for (int i = 0; i < graph[voltex].size(); i++) {
        int nextVoltex = graph[voltex][i];
        if (!isVisited[nextVoltex]) dfs(nextVoltex, 3-color);
    }
}

// 나랑 연결된 친구들은 다른 색이어야 한다.
bool isBipartiteGraph(){
    for (int i = 1; i <= V; i++) {
        for (int j = 0; j < graph[i].size(); j++) {
            int nextVoltex = graph[i][j];
            if (isVisited[i] == isVisited[nextVoltex]) return false;
        }
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    for (int tc = 0; tc < T; tc++) {

        cin >> V >> E;
        for (int i = 0; i <= V; i++) graph[i].clear();
        memset(isVisited, 0, sizeof(isVisited));

        for (int i = 0; i < E; i++) {
            int v1, v2;
            cin >> v1 >> v2;
            graph[v1].push_back(v2);
            graph[v2].push_back(v1);
        }

        for (int i = 1; i <= V; i++) {
            if (!isVisited[i]) dfs(i, RED); // 색을 배정 받지 않은 친구들 탐색
        }

        if (isBipartiteGraph()) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }

    return 0;
}

Reference

백준(1707번) - 이분 그래프