[백준] 2138번 : 전구와 스위치

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

2138번: 전구와 스위치

N=100000이기때문에 모든 전구에 대해서 스위치를 킬지 말지 고려하면 풀수 없다. O(n)만에 풀어야하는 문제다.

 

처음에 생각했던 로직은 메모리초과가 났고, 효율적인 로직이 생각나지 않아 결국 블로그(https://staticvoidlife.tistory.com/143)를 참고하여 풀었다.

 

이 문제는 2가지 케이스로 나누어 풀어야한다. 

1. 0번째 전구를 키고 시작하는 경우

2. 0번째 전구를 키지않고 시작하는 경우

 

이렇게 케이스를 나누어야 O(n)만에 풀수 있다. 

 

맨 앞부터 순차적으로 스위치를 킬지 말지 정해야한다. i번째 전구 상태에 영향을 주는건 i+1전구 밖에 없다는 점을 이해하는게 핵심이였다. 

 

코드는 아래와 같다. 

#include <iostream>
#include <algorithm>
#define INF 987654321
using namespace std;

int N;
string start, target;
int cnt;

void swap(string& s, int i) {//i번째 스위치 누르기
	for (int j = i - 1; j <= i + 1; j++) {
		if (j < 0 || j >= N) continue;
		if (s[j] == '1') s[j] = '0';
		else s[j] = '1';
	}
}

int solve(string a, bool include) {
	int tmpcnt = 0;
	if (include) { //처음 0번째 전구 바꾸고 시작하는 경우
		swap(a, 0);
		tmpcnt++;
	}
	for (int i = 1; i < N; i++) {//1번째~N-1번째 전구 바꾸기
		if (a[i - 1] != target[i - 1]) {//i-1번째 전구에 영향주는건 i번 스위치뿐 
			swap(a, i);
			tmpcnt++;
		}
	}
	if (a == target) return tmpcnt; //만들고자 하는 상태일때 
	else return INF;

}

int main() {
	cin >> N;
	cin >> start >> target;

	cnt = min(solve(start, true),solve(start,false));//0번째 전구 누를때 안누를때 2가지 케이스 
	cout << (cnt == INF ? -1 : cnt) << endl;
}

 

아래는 BFS로 풀고 메모리 초과가 난 코드이다. 효율성을 생각하자.

#include <iostream>
#include <map>
#include <algorithm>
#include <queue>
#define INF 987654321
using namespace std;

int N;
int cnt;
map<string, int> m;
string start, target;
bool finish = false;
queue<string> q;

string swap(string s, int i) {
	for (int j = i - 1; j < i + 2; j++) {
		if (j == -1 || j == N) continue;
		if (s[j] == '0') s[j] = '1';
		else s[j] = '0';
	}
	return s;
}

void solve() {
	while (true) {
		int size = q.size();
		while (size--) {
			string cur = q.front();
			q.pop();
			if (cur == target) {
				finish = true;
				return;
			}
			for (int i = 0; i < N; i++) {
				string s = swap(cur, i);
				if (m[s] != 1) {
					q.push(s);
					m[s] = 1;
				}
			}	
		}
		cnt++;
	}
	
}

int main() {
	cin >> N;
	cin >> start >> target;

	q.push(start);
	m[start] = 1;
	solve();

	cout << (finish? cnt:-1) << endl;

}