문제
https://www.acmicpc.net/problem/16960
풀이
그리디 (오답)
입력으로는 스위치에 연결된 램프들의 번호가 주어진다.
S1 -> L1 L3 L5
S2 -> L2
S3 -> L3 L4 L5
S4 -> L1
나는 이를 역으로 생각해서 램프에 연결된 스위치 번호들을 배열에 저장했다.
L1 -> S1 S4
L2 -> S2
L3 -> S1 S3
L4 -> S3
L5 -> S1 S3
그리고 램프에 연결된 스위치가 1개인 경우, 모든 램프의 불을 켜려면 반드시 눌러야 하므로 우선적으로 스위치를 누르고
연결된 스위치가 2개 이상인 경우에는
- 적어도 하나라도 눌려있으면 패스
- 하나도 눌려있지 않으면 번호가 가장 낮은 스위치부터 누르는
방식으로 그리디하게 풀어봤다.
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 2001;
map<int, int> switches; // 스위치[번호] = 눌림 여부
vector<int> lamp[MAX]; // 램프에 연결된 스위치 번호들
int N, M;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for(int i = 0; i < N; i++){
switches[i + 1] = 0;
}
for(int i = 0; i < N; i++){ // 스위치 개수
int lampCnt; // 연결된 램프 개수
cin >> lampCnt;
for(int j = 0; j < lampCnt; j++){
int num;
cin >> num;
lamp[num].push_back(i + 1);
}
}
int cnt = 0;
// 램프에 연결된 스위치가 1개인 경우 반드시 눌러야 한다.
for(int i = 1; i <= M; i++){
if(lamp[i].size() == 1){
int sn = lamp[i][0];
switches[sn] = 1;
cnt++;
}
}
for(int i = 1; i <= M; i++){
if(lamp[i].size() == 1) continue;
bool pressed = false;
for(auto sn: lamp[i]){ // 최대 N개
if(switches[sn] == 1){
pressed = true;
break;
}
}
// 어떤 스위치도 눌리지 않은 경우
// 가장 번호가 낮은 스위치를 누른다.
if(!pressed){
int sn = lamp[i][0];
switches[sn] = 1;
cnt++;
}
}
cout << (cnt <= N - 1);
return 0;
}그런데 이 방법으로는 최적해를 보장하지 못하는 거 같다.. 오답이 나온다.. 😂
그리고 주어진 문제에서는 N-1 개의 스위치를 눌러서 모든 램프를 켤 수 있는지 묻고 있는데, 위와 같은 풀이는 'N-1 개보다 적은' 스위치로 켤 수 있는 경우도 다루고 있기 때문에 문제 상황에 부합하지 않는 거 같다.
역발상
N개의 스위치를 모두 누르지 않은 상태에서 하나씩 누르는 게 아니라
N개의 스위치를 모두 누른 상태에서 딱 하나를 누르지 않았을 때
즉, N-1개의 스위치로 모든 램프를 켤 수 있는지 생각해보자.
- 스위치에 연결된 램프의 번호
- switches[1] = {1, 2}
- switches[2] = {1, 2, 3}
- 램프에 연결된 스위치의 개수
- lamps[1] = 2
- lamps[2] = 2
- lamps[3] = 1
위와 같은 상황에서 스위치 1번을 누르지 않는다면?
- 스위치에 연결된 램프의 번호
- switches[1] = {}
- switches[2] = {1, 2, 3}
- 램프에 연결된 스위치의 개수
- lamps[1] = 1
- lamps[2] = 1
- lamps[3] = 1
스위치 1번을 누르지 않고도 모든 램프는 연결된 스위치의 개수가 적어도 1개 이상 있으므로 모든 램프는 켜진다.
이처럼 i번째 스위치 하나를 제거했음에도 불구하고 각 램프에 연결된 스위치의 개수가 1개 이상이면 N-1개의 스위치로도 모든 램프를 켤 수 있다고 판단하면 된다.
만약 스위치 하나를 제거했는데 모든 램프가 켜지지 않으면, 그 다음 스위치에 대해 테스트 해보기 위해 제거했던 스위치를 다시 연결해야 한다.
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
// 스위치에 연결된 램프 번호
vector<vector<int>> switches(n + 1);
// 램프에 연결된 스위치 개수
vector<int> lamps(m + 1);
for(int i = 1; i <= n; i++){
int lampCnt;
cin >> lampCnt;
for(int j = 0; j < lampCnt; j++){
int num;
cin >> num;
switches[i].push_back(num);
lamps[num]++;
}
}
for(int i = 1; i <= n; i++){
// 스위치 하나를 제거해본다.
for(auto ln: switches[i]){
lamps[ln]--;
}
bool isAllOn = true;
for(int j = 1; j <= m; j++){
if(lamps[j] <= 0) isAllOn = false;
}
// 그럼에도 모든 램프가 켜져있으면 1 출력
if(isAllOn){
cout << "1\n";
return 0;
}
// 제거했던 스위치를 다시 연결한다.
for(auto ln: switches[i]){
lamps[ln]++;
}
}
cout << "0\n";
return 0;
}N개의 스위치 중에 하나를 제거해보면서 M개의 램프가 모두 켜져있는지 확인하는 과정을 반복하기 때문에 시간복잡도는 O(NM)이 된다. N, M은 최대 2000이어서 TLE가 발생하지 않는다.
참고자료
