14939 불 끄기 https://www.acmicpc.net/problem/14939
N*N 크기의 전구 상태가 주어진다.
모든 전구를 끌때 필요한 횟수를 구하는 문제다.
각각 홍익대, 서강대 플밍 경시대회에 나온 문제다.
시기도 비슷했는데 똑같은 문제가 나왔다.
전구문제만 보면 극혐하는데 (Condition of deep sleep) 고민하다가 힌트를 보고 풀게됬다.
첫행의 전구를 반전시킬 수 있는 경우에는 $2^N$만큼의 경우가 존재한다.
두번째 행부터는 앞서 나온 경우에서 윗행을 꺼야 넘어갈 수 있는 것이 자명하기때문에
윗행을 꺼주는 한가지 경우만 시행해주면 된다.
이렇게 쭉 가다가 N-1 행을 꺼줄 수 있으면 답이 존재하는 것이다.
풀고나서 삼성 S/W 역량테스트에 나올 만한 문제라고 생각됬다.
알고리즘과 적절한 구현력을 평가하기 좋은 문제이기 때문이다.
이번 교내 경시대회 문제가 꽤 괜찮은데 남은 문제도 풀어봐야겠다.
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N;
int map[19][19];
int rowInfo[19];
vector<pair<int,int>> v;
int ans = 0x3f3f3f3f;
void init(int idx, int info, int cnt) {
if (idx == N) {
v.push_back({ info, cnt });
return;
}
init(idx + 1, info | (1 << idx), cnt + 1);
init(idx + 1, info, cnt);
}
void solve(int y, int prev, int here, int cnt) {
if (y == N) {
if (prev == 0 && cnt < ans) ans = cnt;
return;
}
if (y == 0) {
for (auto &i : v) {
int nprev = rowInfo[y];
int nhere = rowInfo[y + 1];
for (int n = 0;n < N;n++) {
if (i.first &(1 << n)) {
if (n - 1 >= 0) nprev ^= (1 << (n - 1));
if (n + 1 < N) nprev ^= (1 << (n + 1));
nprev ^= (1 << n);
nhere ^= (1 << n);
}
}
solve(y + 1, nprev, nhere, cnt + i.second);
}
}
else {
int nprev = here;
int nhere = rowInfo[y + 1];
int ncnt = 0;
for (int n = 0;n < N;n++) {
if (prev &(1 << n)) {
ncnt++;
if (n - 1 >= 0) nprev ^= (1 << (n - 1));
if (n + 1 < N) nprev ^= (1 << (n + 1));
nprev ^= (1 << n);
nhere ^= (1 << n);
}
}
solve(y + 1, nprev, nhere, cnt + ncnt);
}
}
int main() {
scanf("%d", &N);
for (int n = 0;n < N;n++) for (int m = 0;m < N;m++) {
scanf("%d", &map[n][m]);
if (map[n][m]) rowInfo[n] |= (1 << m);
}
init(0, 0, 0);
solve(0, 0, 0, 0);
printf("%d\n", ans == 0x3f3f3f3f ? -1 : ans);
return 0;
}
| cs |
접근 방법에 여쭤보고 싶은데 가능할까요?
답글삭제우선 첫번째 행일때의 경우에 대해 생각해보면 전구를 반전시키는 작업을 총 2^N의 경우의 수가 나올겁니다.
답글삭제(전구를 반전시키는 작업을 1이라 하고 N이 3일때 첫번째 행을 반전시키는 경우의 수는 {000,001,010,011,100,101,110,111})
그다음 행으로 넘어가면 전구를 반전시키는 경우는 정해질 수 밖에 없습니다.
전구를 반전시키면 영향을 받는 전구들은 위,아래,오른쪽,왼쪽인데 같은 열 위의 행에서 켜진 전구는 현재 상태에서 반전시킬 수 밖에 없기때문이죠.
그래서 2^N의 경우의 수를 구해서 반전시키는 전구의 수중 최솟값이 답이됩니다.
혹시 코드 설명 간략하게 부탁드려도 될까요? 댓글에 있는 접근 방법을 봐도 잘 모르겠어서요..
답글삭제init함수에서는 첫 행에서 반전시킬 수 있는 모든 경우인 2^N의 경우의 수를 모두 구해줍니다.
삭제(v에는 bitmask형태로 반전시킨 정보를 저장해있고 반전시킨 횟수또한 저장되있습니다.)
그 후 solve함수에서는 첫행에서 반전시킨 정보들에 의존해서 다음 행들에서 꺼야 하는 전구들을 순차적으로 구하는 부분을 의미합니다.
설명을 잘 못해서 죄송합니다 ㅠㅠ
solve함수에서 꺼야하는 전구를 구할 때 그 전구의 위치도 같이 저장하고 싶은데 어떻게 해야할까요?(최종적으로 끄는 횟수 뿐만 아니라 전구의 위치도 같이 출력해서 보고 싶습니다)
삭제y==0일 때 저는 v(2^n의 경우의 수가 들어있는 bitmask)의 경우의 수를 돌려주는데
삭제solve함수를 돌려보면서 가장 끄는 횟수가 적은 경우의 bitmask를 저장할 수 있습니다.
int pans = ans;
solve(y + 1, nprev, nhere, cnt + ncnt);
if(ans < pans) //ans가 더 작은값으로 갱신되었다면 bitmask 저장
save = i.first;
그 후에 그 경우에 대해서 한번 돌려주면서 출력 및 저장하면 될거같습니당
죄송해요 상태 저장하는 것에대해서 이해를 못하겠어요.. 설명 다시 한번만 부탁드려도 될까요?
삭제정리하자면 이 문제는 첫행에서 스위치를 끄는 2^n경우만 구하면 답을 구할 수 있는 문제입니다.
삭제이전행에서 스위치가 켜져있다면 현재위치에서 눌러서 꺼야하는 의존적인 관계이기 때문이죠.
solve함수를 통해 모든 경우의 수를 구해서 가장 적게 스위치를 눌러 불을 끄는 횟수를 구합니다.
이때 solve함수를 제가 댓글에 단 방식처럼 수정을 하면 save변수에는 가장 적게 스위치를 누르는 경우에 대한 첫행을 어떻게 반전시켜야하는지 bitmask형태로 정보가 저장됩니다.
save변수로 어떠한 전구를 꺼야하는지 구할 수 있습니다.
함수를 하나 더 만들어서(solve함수에서 vector에 넣으면서 잘 관리하면 굳이 함수를 새로 만들 필요는 없긴합니다)
solve함수처럼 재귀적으로 구현하면 어떠한 전구를 켜야할지를 구할 수 있게 됩니다.