16960 스위치와 램프 (C++)

스위치와 램프

모든 램프가 켜지는지 확인하는 문제

문제를 제대로 안읽어서 시간이 좀 걸렸다

1. 문제

---

간단 설명

N개의 버튼이 주어진다

각 버튼은 램프와 연결이 되어있는데

한개와 연결되어있을수도, 여러개와 연결되어있을수도, 혹은 아예 연결이 안되어있을수도 있다

N개의 스위치를 모두 누르면 모든 램프가 켜진다

N-1개의 스위치를 눌렀을 때, 모든 램프가 켜지는지를 확인하는 문제

2. 문제 분석

---

주의점

• 버튼은 한번 누르면 램프는 꺼지지 않는다. 스위치를 이용해서 램프의 전원을 끌 수는 없다.

• 스위치에 램프가 연결이 아예 안되어있을수도 있음

• 램프가 모두 켜져있는지를 확인하는 시점이 중요

필요변수

스위치의 개수 int N, 램프의 개수 int M (둘다 2000 이하)

스위치와 연결된 램프 번호를 저장할 2차원 벡터 연결 리스트 lamp_switch[i][j]

램프의 상태를 저장할 bool lamp[MAX]

알고리즘

1. 입력받기
    - N, M입력 받고
    - 연결리스트 정보를 입력받아 연결 정보를 저장한다
2. 1번째 버튼부터 2000번째까지 순차적으로 해당 버튼을 제외하고 다 눌러본다
    2-1. 램프를 모두 끈 상태로 초기화한다
    2-2. i번째 버튼을 제외하고 눌러본다
    2-3. 모두 켜졌다면 1을 출력하고 종료한다
    2-4. 모두 켜지지 않았다면 2번으로 돌아간다
3. 다 돌아봤는데 안된다면 0을 출력하고 종료

3. 소스코드

---

#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define MAX 2010

int N, M;
vector<vector<int>> lamp_switch;
bool lamp[MAX];

void Input() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> M;
	lamp_switch.resize(N);
	for (int i = 0; i < N; i++) {
		int size_for_switch;
		cin >> size_for_switch;
		lamp_switch[i].resize(size_for_switch);

		for (int j = 0; j < size_for_switch; j++) {
			cin >> lamp_switch[i][j];
		}
	}
}

bool Check() {
	for(int i=1; i<=M; i++){
		if (lamp[i] == false) {
			return false;
		}
	}
	return true;
}

int main() {
    // 1. 입력받기
	Input();

	// 2. i번째 버튼을 제외하고 눌러봄
	for (int i = 0; i < N; i++) {
		memset(lamp, 0, sizeof(lamp)); // 램프 초기화

		// i 번을 제외하고 다 눌러본다
		for (int j = 0; j < N; j++) {
			if (i == j) continue;
			for (int k = 0; k < lamp_switch[j].size(); k++) {
				lamp[lamp_switch[j][k]] = true;
			}
		}

		// 모두 켜졌다면
		if (Check()) {
			cout << "1" << endl;
			return 0;
		}
	}

    // 3. 다 돌아봤는데 안된다면 0을 출력하고 종료
	cout << "0";

	return 0;
}

문제를 제대로 이해하지 않고 바로 풀려고 했다가

뭔가 이상함을 깨닫고 다 뜯어 고침

N개의 스위치를 누르면 모두 켜지는지 확인하는 문제인줄 알았다

또 램프가 토글형식인줄 알고 고민했다가

스위치를 이용해서 램프의 전원을 끌 수는 없다.라는 문구를 나중에 봤다

문제를 꼼꼼히 읽자