[백준] No.16915 - 호텔 관리 (C++, 2-SAT)

문제

 

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

16915번: 호텔 관리

 

 

풀이

 

solved.ac 난이도: Platium 3

 

 

2-SAT 문제에 대하여 모른다면 반드시 먼저 공부하고 옵시다.

[2-SAT] 2 - Satisfiability Problem / 충족 가능성 문제 (알고스팟 회의실 배정 풀이)

 

이번 문제는 (A || B) &&(B || C) && (C || D) 와 같은 논리곱 정규형(Conjunctive normal) 식을 어떻게 만들어 내는 지가 중요했습니다.

 

각 호텔의 방은 두 개의 스위치와 연결되어 있고, 연결된 두 스위치들을 스위치들을 누르거나 누르지 않는 선택을 하는 2-SAT유형의 문제입니다.

 

일단 닫혀있는 방을 생각해봅시다.

해당 방과 연결된 스위치를 A와 B라고 할때 방을 열기위해서는

단 하나의 스위치만을 눌러야합니다.

따라서 논리 식은 다음과 같습니다.

 

(A||B) && (!A||!B) 가 참이 되기 위해서

 

(A||B)에 의해

!A => B : A가 눌리지 않으면 B가 눌려야한다.

!B => A : B가 눌리지 않으면 A가 눌려야 한다.

 

(!A||!B)에 의해

A => !B : A가 눌리면 B는 눌러서는 안된다.

B => !A : B가 눌리면 A는 눌러서는 안된다.

 

 

이번에는 열려있는 방을 생각해 봅시다.

 

열려 있는 방에 연결된 스위치 A와 B는 하나만 눌려서는 안됩니다.

한개의 스위치를 누르면 해당 방을 다시 열기위해 다른 스위치 하나를 마저 눌러주어야 합니다.

따라서 스위치를 두개 다 누르지 않거나 두개 다 눌러 줍시다.

 

(!A||B) && (A||!B) 가 참이 되기 위해서

 

(!A||B)에 의해

A => B : A가 눌리면 B도 눌려야한다.

!B => !A : B가 눌리지 않으면 A도 눌러서는 안된다.

 

(A||!B)에 의해

!A => !B : A가 눌리지 않으면 B도 눌러서는 안된다.

B => A : B가 눌리면 A도 눌러야 한다.

 

이러한 함의 그래프를 생성하기 위한 코드는 다음과 같습니다.

 

  adj = vector<vector<int>>(switch_num*2);
 
  int a,b, not_a, not_b;
  for(int i=0; i<room_num ; ++i){   //함의 그래프 생성
    a = connected_switch[i][0]*2;
    b = connected_switch[i][1]*2;
    not_a = a+1; not_b = b+1;
 
    if(room_state[i] == 0){
 
      adj[not_a].push_back(b);
      adj[not_b].push_back(a);
 
      adj[a].push_back(not_b);
      adj[b].push_back(not_a);
    }else{
      adj[a].push_back(b);
      adj[b].push_back(a);
 
      adj[not_a].push_back(not_b);
      adj[not_b].push_back(not_a);
    }
  }

 

그래프 생성이 완료됬다면 SCC를 진행하여 A와 !A가 같은 SCC에 존재하지 않는 모든 경우

해당 식은 정답을 가집니다. 

 

 

코드