문제 이해 단계
https://www.acmicpc.net/problem/21277
설명만 읽어보면 무슨 소리인지 전혀 모르겠다.
예제 입력과 그에 대한 해설을 보니까 어느 정도 이해되더라.
퍼즐 1과 퍼즐 2의 행과 열의 크기가 정보로 들어오고,
퍼즐 1과 퍼즐 2의 배열 상태가 입력으로 또 들어온다.
두 블록을 한 액자에 넣으려고 퍼즐 1과 퍼즐 2를 90도씩 돌려가면서
최대한 넓이를 작게 만드는 것이 목표이다.
넓이를 작게 만든다는 말은
퍼즐 1의 0으로 된 부분에 퍼즐 2의 1로 된 부분이 들어가는데,
퍼즐 1의 1 부분과 퍼즐 2의 1 부분이 서로 겹치지 않는 것이다.
이때의 이때의 나올 수 있는 최소의 넓이는 구하는 문제
문제 접근 단계
이 문제에서는 제한 사항에 큰 힌트가 있다.
퍼즐의 가로와 세로 길이가 각각 50 이하라는 것이다.
퍼즐을 돌리는 경우의 수를 생각하더라도 90도씩 총 4번이기 때문에
50*50*4 그리고, 겹치는지 아닌지 판단할 때
최악은 모든 배열을 보는 것이기 때문에 50*50이다.
즉 모두 곱해보면 50^4*4 = 25* 10^6이다.
천만단위밖에 가지 않기 때문에 1초가 넘지 않는다.
따라서 해당 문제는 브루트포스로 접근하여 일일이 비교하는 것이 가능하다.
어떻게 탐색하는 것이 편할까?
브루트포스로 접근하면 된다는 것을 알았기 때문에 무식하게 해 본다.
그냥 퍼즐 1과 퍼즐 2의 겹치는 부분이 1로 동일하다면 그 위치는 안 되는 위치다.
이렇게 생각한다.
이렇게 생각할 때 탐색을 한다고 생각하면,
당연히 두 개 중 하나를 고정하고 하나면 움직이는 게 편하다.
그래서 퍼즐 1을 고정시키고 퍼즐 2만 움직인다고 가정한다.
구할 수 있는 넓이 경우의 수
최종적으로 우리가 구해야 하는 것은 두 퍼즐이 겹칠 때의 넓이이다.
이렇게 생각했을 때, 나올 수 있는 경우의 수는 한정적이다.
정확히는 넓이가 달라지는 조건이라는 것이 존재한다.
위 그림에서 연두색 사각형은
퍼즐 1, 파란색 사각형은 퍼즐 2를 뜻한다.
위 경우는 모두 퍼즐 2가
퍼즐 1 안에 속해있을 때의 경우이다.
이런 경우 퍼즐 1의 행과 열의 길이에 의해 넓이가 결정된다.
이 경우는 퍼즐 2가
퍼즐 1에 들어맞긴 하지만 튀어나온 경우들이다.
이런 경우 퍼즐 2의 튀어나온 높이와 너비 정도를 계산하여
넓이를 구해줘야 한다.
이 경우는 좀 복잡한 경우이다.
왜냐하면 튀어나온 높이와 너비를 직접 계산해야 하기 때문이다.
이제 다음을 살펴보자.
이 경우는 퍼즐 2가 퍼즐 1안에 들어맞는 것이 없어서
그냥 옆에 붙인 것이라고 보면 편하다.
이런 경우의 넓이는 두 퍼즐의 합과 차 정도로 쉽게 구할 수 있을 것 같아서
걸쳐있을 때보다는 쉬워 보인다.
또 다른 경우의 수가 있을까?
그러니까 안쪽, 걸쳐있을 때, 딱 맞을 때까지 했으니까..
이제 떨어졌을 때??
그렇지 않다.
떨어졌을 때는 애초에 문제 성립 자체가 되지 않는다.
왜냐하면 딱 붙이는 방법은 무조건 가능한 방법이고,
떨어뜨리는 방법보다는 무조건 작기 때문이다.
즉, 나올 수 있는 경우는 위에서 언급한 3가지 밖에 없다.
퍼즐을 비교해서 해당 자리가 들어맞을 때,
어떤 형태로 있는지를 인식하고 넓이를 구해야 한다.
고정시키는 위치
난 탐색을 편하게 하기 위해서 퍼즐 1은 고정시킨다고 했는데,
이 퍼즐을 어디에 고정시키는 게 좋을까?
뜬금없다고 느낄 수 있다.
당연히 2차원 배열을 만들면 (0,0)에 고정될 것이고 이게 편할 텐데..
근데 이 문제는 그렇게 하면 안 된다.
왜냐하면 바로 위의 경우의 수에 이것 때문이다.
만약 퍼즐 2가 퍼즐 1 앞에 위치한다면?
인덱스가 음수로 갈 수 없기 때문에 에러가 날 것이다.
그래서 고정시킬 위치를 고민해줘야 한다.
필자는 그냥 마음 편하게 제한조건을 이용하기로 했다.
제한조건에서 가로, 세로가 50 이하이기 때문에 (50,50)을
원점으로 잡아두면 그 어떤 퍼즐 2도 음수로 갈 수 없다.
그래서 퍼즐 1 가로와 세로에 50씩 더해서 50,50에 고정시켜 뒀다.
그 후 그에 맞춰 탐색을 진행해 주면 된다.
이 이후로부터는 배열 인덱스를 가지고 하는
정밀한 작업이기 때문에 사실상 코드 설명이 주다.
그래서 말로 하는 설명보다는 코드를 보는 게 이해가 빠르다.
그래서 코드 구현 단계에서 설명하겠다.
문제 구현 단계
int N1,M1; // 퍼즐1의 (x,y)
int N2,M2; // 퍼즐2의 (x,y)
bool map[150][150] = {0,}; // 맵의 전체 크기
bool puzzles1[50][50] = {false,};
bool puzzles2[50][50] = {false,};
// 두 퍼즐이 겹치는지 비교
int comparePuzzle(int x, int y){
bool isFlag = false;
for(int i = x; i < x+N2; i++){
for(int j = y; j < y+M2; j++){
// 같은 위치에서 둘다 1일 경우
if((map[i][j] && puzzles2[i-x][j-y])) {
isFlag = true;
break;
}
}
if(isFlag) break;
}
if(!isFlag){
return getMaxSize(x,y); // 넓이 구하는 함수 호출
}
return INT32_MAX;
}
int getMaxSize(int x, int y){
int minX = min(x,50); // 퍼즐1에서 나올 수 있는 가장 작은 X값 = 50
// 퍼즐2에 최대 세로 길이 vs 퍼즐 1의 최대 세로 길이
int maxX = max(x+N2-1,50+N1-1);
int minY = min(y,50); // minX와 같음
// maxX와 가로 세로만 다름
int maxY = max(y+M2-1,50+M1-1);
int width = maxY - minY + 1;
int height = maxX - minX + 1;
return width * height;
}퍼즐 탐색과 넓이를 구하는 핵심 함수이다.
둘 다 매개변수로 퍼즐 2의 시작좌표를 받는다.
comparePuzzle부터 살펴보면 Map 현재 지점부터
퍼즐 2의 길이만큼 하나하나씩 탐색하여 겹치는 것이 있는지 체크한다.
겹치는 것이 있으면 isFlag = true 하고
나올 수 있는 최댓값을 반환하고 끝낸다.
겹치는 것이 없는 경우만 getMaxSize를 호출한다.
이는 현재 퍼즐 2의 위치로 넓이를 계산한다.
여기서 minX는 x와 50을 비교하는데,
x는 퍼즐 2의 시작 위치이기 때문에 가장 작은 값일 수밖에 없다.
그리고 50 또한 퍼즐 1의 원점이기 때문에 가장 작은 값이다.
사실 위 말의 뜻은
퍼즐 2의 가장 작은 x과 퍼즐 1의 가장 작은 x 중 어느 게 더 작은가?
를 묻는 것이다.
minY 또한 같은 원리이다.
설명은 생략한다.
maxX는 좀 더 복잡하게 되어있는데,
그냥 x가 시작위치이기 때문에
끝위치로 옮기기 위해 가로길이 N2만큼 더한 거다.
그리고 길이를 더했고,
인덱스는 0부터 시작하기 때문에 1을 빼준 것이다.
50+M1-1 또한 마찬가지로 퍼즐 1의 세로길이에
원점인 50을 더해주고 1을 빼준 것이다.
이것도 결국 퍼즐 1과 퍼즐 2의 가장 긴 x값 중
어느 게 더 긴가?를 묻는 것이다.
이렇게 최댓값과 최솟값을 구해주고
서로 빼줘서 길이를 구해주고 곱해주면 된다.
// 퍼즐2 회전
void rotate(){
bool cmap[50][50];
// 배열 복사
copy(&puzzles2[0][0],&puzzles2[0][0]+2500, &cmap[0][0]);
for(int i = 0; i < N2; i++){
for(int j = 0; j < M2; j++){
puzzles2[j][N2-i-1] = cmap[i][j];
}
}
swap(N2,M2); // 가로, 세로가 바뀌었기 때문에 뒤집음
}rotate는 시계 방향으로 90도씩 회전한다.
회전을 위해 cmap에 map을 복사하여 담아두고
순차적으로 모든 행과 열을 훑는다.
시계 방향으로 움직일 때
열은 오름차순, 행은 내림차순으로 움직이기 때문에
저런 방식으로 구할 수 있다.
그리고 마지막에 봐야 할 것은
가로, 세로가 바뀌었기 때문에
N2와 M2도 바꾸어줘야 한다는 것이다.
핵심적인 함수에 대한 설명은 여기서 끝이고,
아래에 부수적인 설명이 담긴 전체코드에 대해 올리고 끝내겠다.
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
#define endl "\n";
int comparePuzzle(int,int);
int getMaxSize(int,int);
int N1,M1; // 퍼즐1의 (x,y)
int N2,M2; // 퍼즐2의 (x,y)
bool map[150][150] = {0,}; // 맵의 전체 크기
bool puzzles1[50][50] = {false,};
bool puzzles2[50][50] = {false,};
// 두 퍼즐이 겹치는지 비교
int comparePuzzle(int x, int y){
bool isFlag = false;
for(int i = x; i < x+N2; i++){
for(int j = y; j < y+M2; j++){
// 같은 위치에서 둘다 1일 경우
if((map[i][j] && puzzles2[i-x][j-y])) {
isFlag = true;
break;
}
}
if(isFlag) break;
}
if(!isFlag){
return getMaxSize(x,y); // 넓이 구하는 함수 호출
}
return INT32_MAX;
}
int getMaxSize(int x, int y){
int minX = min(x,50); // 퍼즐1에서 나올 수 있는 가장 작은 X값 = 50
// 퍼즐2에 최대 세로 길이 vs 퍼즐 1의 최대 세로 길이
int maxX = max(x+N2-1,50+N1-1);
int minY = min(y,50); // minX와 같음
// maxX와 가로 세로만 다름
int maxY = max(y+M2-1,50+M1-1);
int width = maxY - minY + 1;
int height = maxX - minX + 1;
return width * height;
}
// 퍼즐2 회전
void rotate(){
bool cmap[50][50];
// 배열 복사
copy(&puzzles2[0][0],&puzzles2[0][0]+2500, &cmap[0][0]);
for(int i = 0; i < N2; i++){
for(int j = 0; j < M2; j++){
puzzles2[j][N2-i-1] = cmap[i][j];
}
}
swap(N2,M2); // 가로, 세로가 바뀌었기 때문에 뒤집음
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N1 >> M1;
for(int i = 0; i < N1; i++){
string str;
cin >> str;
for(int j = 0; j < M1; j++){
puzzles1[i][j] = str[j]-'0';
}
}
cin >> N2 >> M2;
for(int i = 0; i < N2; i++){
string str;
cin >> str;
for(int j = 0; j < M2; j++) puzzles2[i][j] = str[j] - '0';
}
int ans = INT32_MAX;
int k = 4;
for(int i = 50; i < 50 + N1; i++){
for(int j = 50; j < 50+ M1; j++) map[i][j] = puzzles1[i-50][j-50];
}
while(k--){
for(int i = 0; i < 100; i++){
for(int j = 0; j < 100; j++){
ans = min(ans,comparePuzzle(i,j));
}
}
rotate();
}
cout << ans << endl;
}90도씩 도는 것은 총 4번 발생하기 때문에
k = 4에서 시작하여 총 4번을 돌린다.
시행착오
이 문제 또한 풀지 못했다.
배열 돌리기까지는 이제 익숙해져서
금방 하지만 역시 다른 부분이 문제다.
구현 문제는 다른 사람의 코드를
내 것으로 가져오는 게 너무 힘들다.
이 것도 완전히 이해하는데 오래 걸렸다.
구현 문제만 이런 지는 모르겠는데,
풀이를 봐도 너무 오래 걸린다.
시간 효율이 너무 안 나온다.
점점 자괴감이 많이 든다.
환기가 필요한 시점인가? 근데 불안함ㅋㅋ
남들에 비해 나만 뒤처지는 느낌이 크다.
나는 확실히 이해력이 떨어진다. 그래서 더 열심히 해야 한다.