05 Sep 2021
난이도
Gold II
문제 풀이
딱 보고 생각나는 풀이는, 벽을 없애고 Flood Fill로 몇개인지 세어서 답을 구하는 풀이이다. 근데, 그렇게 짜면 TLE를 받는다.
5 5
00000
01010
00000
01010
00000
이런식의 데이터가 주어졌다고 해보자. 벽인 부분에서 Flood Fill을 해서 개수를 구하면, 거의 모든 공간에 대해 Flood Fill을 수행하게 됨을 파악할 수 있다. 최악의 경우를 생각해보면, 모든 지점에서 검사하는데에 \(\scriptsize O(NM)\)이고, Flood Fill이 거의 모든 지점에 되어야 하기에 거기서 \(\scriptsize O(NM)\)이다. 따라서, \(\scriptsize O(NM) * O(NM) = O(N^{2}M^{2})\)이다. 최대 \(\scriptsize 10^{12}\)만큼의 연산이 수행될 수 있으니, 직관적인 풀이로는 불가능함을 알 수 있다.
그럼 어떻게 풀면될까? Flood Fill을 수행하는 \(\scriptsize O(NM)\)만큼이 문제이니, 이걸 최대한 줄여보자.
5 5
11111
01110
00100
01110
11111
같은 데이터를 생각해보자. 만약 (2, 2)지점에 있는 벽(정중앙)을 지우고 갈 수 있는 칸의 개수를 센다고 생각해보자. 벽을 지웠으니 먼저 1개이고, 좌측으로는 4개, 우측으로도 4개의 칸이 있음을 알 수 있다. 상하로는 벽이 있어 갈 수 있는 칸이 없기에, 답은 1 + 0 + 0 + 4 + 4(현재 지점 + 상 + 하 + 좌 + 우)임을 알 수 있다. 즉, 벽이 있는 칸에서 상하좌우에 몇개의 칸들이 각각 집합을 이루고 있는지만 알면 되지 않은가? 이걸 그대로 구현해주면 된다. 그런데, 이렇게만 구현하면 상하좌우가 같은 집합에 속하는 경우에 중복으로 카운트하게 된다. 그렇기에 이미 센 집합이면 걸러주어야 함을 유의하며 코드를 작성하면 된다.
집합들을 구해주는 것은 Flood Fill로 해결해주면 된다. 나는 Flood Fill을 BFS로 구현했고, 각 영역에 대해 번호를 붙여 구별되도록 했다. 또한, 그 영역번호를 통해 해당 영역에 얼마만큼의 칸들이 집합을 이루는지도 알 수 있도록 집합 개수를 저장했다.
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int id = 1; //다른 영역을 구분하기 위한 영역번호
vector<int> setCount; //특정 영역에 몇개의 칸들이 집합을 이루는지 저장
vector<vector<bool>> visit; //BFS 방문 여부
vector<vector<int>> sameSet; //어떤 지점이 어느 영역에 속하는지 알기 위한 2차원 벡터
void floodFill(vector<vector<int>>& map, int y, int x) {
int cnt = 1;
queue<pair<int, int>> q;
visit[y][x] = true;
sameSet[y][x] = id; //(x, y)에 해당하는 영역 번호 표시
q.push({x, y});
while(!q.empty()) {
int curX = q.front().first;
int curY = q.front().second;
q.pop();
for(int i = 0; i < 4; ++i) {
int nextX = curX + dx[i];
int nextY = curY + dy[i];
if(nextX < 0 || nextX >= M || nextY < 0 || nextY >= N) continue;
if(visit[nextY][nextX] || map[nextY][nextX] == 1) continue;
cnt++;
sameSet[nextY][nextX] = id; //(nextX, nextY)에 해당하는 영역 번호 표시
visit[nextY][nextX] = true;
q.push({nextX, nextY});
}
}
id++;
setCount.push_back(cnt); //BFS가 끝나면, 해당 집합을 이루는 칸들의 수를 저장함.
}
즉, 위의 코드를 가지고 아래의 데이터에 적용해 나타내본다면 다음과 같다.
3 3 sameSet idx : 0 1 2 3 4
101 -> 010 -> setCount = {-1, 1, 1, 1, 1}
010 203 //0번째 인덱스는 사용하지 않기에 -1로 표시
101 040
모든 빈 칸에서 Flood Fill을 수행하고, 그 이후 모든 벽인 칸들에 대해서 개수를 세면 된다. 자세한 코드는 아래와 같다.
for(int i = 0; i < N; ++i) {
for(int j = 0; j < M; ++j) {
if(map[i][j] == 0 && !visit[i][j]) floodFill(map, i, j); //방문하지 않은 모든 빈칸에서 Flood-Fill수행
}
}
for(int y = 0; y < N; ++y) {
for(int x = 0; x < M; ++x) {
if(map[y][x] == 1) { //모든 벽인 칸들에 대해 개수를 구하기
int cnt = 1; //벽을 빈칸으로 바꾸기에 1부터 시작
vector<int> counted; //중복 카운팅 방지
for(int i = 0; i < 4; ++i) { //상하좌우 체크
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= M || ny < 0 || ny >= N) continue; //범위 밖이면 건너뛰기
if(map[ny][nx] == 1) continue; //벽이면 건너뛰기
if(find(counted.begin(), counted.end(), sameSet[ny][nx]) != counted.end()) continue; //만약 이미 센 영역번호라면 건너뛰기
cnt += setCount[sameSet[ny][nx]]; //해당 영역번호에 있는 칸들의 개수 더하기
counted.push_back(sameSet[ny][nx]); //중복 카운팅 방지를 위해 이미 센 영역번호 저장
}
cnt %= 10;
cout << cnt; //카운트 출력
}
else cout << 0; //벽이 아니면 0 출력
}
cout << '\n';
}
엄청 어려운 아이디어가 필요한 문제는 아니였으나, 생각나는대로만 풀었다간 TLE받고 의아할 수 있는 문제이다. 나도 그냥 딱 보고는 쉬운 문제같네 싶어서 바로 풀었더니, TLE받고 “왜지??” 하고 한참 생각하고 있었다..
코드 전문
16946 // 벽 부수고 이동하기 4
03 Sep 2021
난이도
Gold II
문제 풀이
문제 이름부터 뭔가 수학스럽다. 그래서 수학적으로 접근을 해보자.
집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다.
간단하게 설명해보자면, 어떤 집합 P의 벡터매칭은 그 집합의 모든 원소들을 한번씩 사용해 만들어진 벡터들의 집합이라는 것이다. 우리가 구해야하는 것은 이 벡터매칭에 있는 벡터들의 합의 길이의 최솟값이다. 벡터매칭의 벡터들을 모두 다 더했을때, 그 합벡터의 크기가 어떻게 하면 최소가 되느냐를 묻는 것이다.
간단히 생각하면, 모든 벡터매칭 집합들을 다 만들어서 최솟값을 구하면 답이 나온다. 두 점씩 잡아 벡터를 만들어 합벡터에 더하고 하는 식으로 하면 물론 답은 나올 것인데, 그게 좀 복잡하고 생각하기 어려운것 같아서 살짝 다른 관점에서 보면 어떨까? 만들어서 더하는게 아니고 그냥 합벡터 그 자체를 한번 생각해보자.
\[\small \overrightarrow{P}= \left ( \sum_{} x_{i}, \sum_{} y_{i} \right )\]
벡터의 x성분은 x성분대로 더하고, y성분은 y성분대로 더하면, 그게 합벡터이다. 근데, 이걸 조금만 뜯어서 살펴보면,
\[\small \overrightarrow{P} = \left ( \sum_{a}x_{a} - \sum_{b}x_{b},\sum_{a}y_{a} - \sum_{b}y_{b} \right )\]
위 수식처럼 쓸 수 있다. 여기서 a는 어떤 벡터의 끝점에 해당하는 것이고, b는 어떤 벡터의 시작점에 해당하는 것이라 생각하면, 자연스럽게 그 의미를 파악 할 수 있다. 벡터를 만들때, 끝점에서 시작점을 빼서 표현하는데(정확히는 끝점을 가르키는 벡터에서 시작점을 가르키는 벡터의 차) 그것을 그대로 쓴 것이다.
먼저, 끝점과 시작점의 개수는 동일하므로 a = b이고 a = b = n / 2 인 것을 간단하게 파악할 수 있다. 저 식에 의하면, 그냥 a = n / 2개의 점들만 결정해주면 b는 알아서 결정되니, 끝점들만 선택해주는 것으로 벡터를 결정할 수 있음을 알 수 있다. 즉, n / 2개의 점만 결정해준다면 벡터를 쉽게 만들 수 있다.
이때, n는 문제에서 최대 20이라 주어졌기에, 최대 \(\scriptsize C(20, 10)\)가지의 경우의 수가 존재하게 된다. 이 숫자는 대충 \(\scriptsize 1.8 \cdot 10 ^ {5}\)정도 이기에 충분히 시간내에 풀 수 있다.
const double INF = 987654321.0;
double solve(vector<pair<double, double>>& seq, vector<bool> chosen, int cnt, int size, int startIdx) {
//base
if(cnt == size / 2) {
double frontX = 0, backX = 0, frontY = 0, backY = 0;
for(int i = 0; i < size; ++i) {
if(chosen[i]) {
frontX += seq[i].first;
frontY += seq[i].second;
}
else {
backX += seq[i].first;
backY += seq[i].second;
}
}
double X = frontX - backX;
double Y = frontY - backY;
return sqrt(pow(X, 2) + pow(Y, 2));
}
//combination
double ret = INF;
for(int i = startIdx; i < size; ++i) {
if(!chosen[i]) {
chosen[i] = true;
ret = min(ret, solve(seq, chosen, cnt + 1, size, i));
chosen[i] = false;
}
}
return ret;
}
n / 2개의 점을 선택해 합벡터를 구하고 그 크기의 최솟값을 구하는 코드이다. 먼저, seq는 좌표값이 들어있는 벡터이고, chosen은 몇 번째의 좌표점이 선택되었는지 나타내어주는 bool형 벡터이다. 기저사례는 n / 2개의 점이 선택된 경우이니, 그 때 합벡터를 계산해서 값을 구해 리턴해주면 되는 것이다. 그 이외의 경우에는 점들을 선택해 조합을 만들어나가도록 코드를 짜면 해결된다.
나는 처음에 시간초과를 받았는데, 처음 제출한 코드에는 startIdx라는 파라미터가 없었기 때문이다. 이 파라미터가 해주는 일은 앞에서 선택했던 원소들을 거르고 뒤에서부터 선택을 해주게 한다. 이게 없으면.. 같은 경우를 매우 많이 조사하기 때문에, 시간복잡도가 지수적으로 늘어나게 된다. 이 파라미터를 사용해 범위를 제한해 준다면, 시간복잡도는 \(\scriptsize O(C(N, \frac {N} {2}) \cdot T)\)이다. N는 점의 개수이고, T는 테스트케이스 개수이다.
조합을 짤 때에는 항상 의도한 시간복잡도를 가지는지 체크해볼 필요가 있는 듯 하다.. 그렇지 않으면, 나처럼 뻘짓하고 있을테니 유의.
코드 전문
1007 // 벡터 매칭
22 Aug 2021
난이도
Gold V
문제 풀이
딱 문제를 봤을 때는 DFS나 BFS를 활용해 풀 수 있다고 생각했다. 실제로도 백 트래킹과 그래프 탐색 알고리즘을 활용하면 길지 않은 시간에 이 문제가 풀린다. 그래서 처음에는 BFS를 활용해서 풀려고 시도했는데.. 구현력이 좀 딸렸던건지 잘 안 풀려서 방향을 틀었다. 내가 선택한 방법은 3차원 배열을 사용하는 DP이다. 먼저, 파이프가 가질 수 있는 상태를 먼저 살펴보자.
파이프가 세로로 놓여진 경우 이전의 상태는 두가지 경우가 있다. 첫번째는 세로 상태로 놓여졌던 경우, 두번째는 대각 상태로 놓여졌던 경우이다. 그럼, 그 두가지가 되기 위한 경우의 수를 더하면 지금 세로로 놓여진 상태의 경우의 수가 되지 않겠는가? 이런식으로 나머지 경우들도 살펴보자.
다음으론 가로로 놓여진 경우이다. 같은 방법으로, 이전의 상태는 가로와 대각이 가능하다. 즉, 가로로 놓여진 경우의 수 = (이전)가로로 놓여진 경우의 수 + (이전)대각으로 놓여진 경우의 수 인 셈이다.
마지막으로, 가장 까다로운 부분인 대각으로 놓여진 경우이다. 앞의 두 경우들과 다르게 점유하는 영역이 더 넓기에 그 부분까지도 코드에 체크해줘야 한다. 아무튼 체크했다고 생각해보면, 대각 = (이전)(세로 + 대각 + 가로) 인 셈이다. 이걸 파악하고 나면, 어떻게 DP를 해야할지 감이 오지 않는가?
먼저 파이프의 상태(세로, 대각, 가로)를 숫자로 표현하자. 나는 세로-대각-가로를 각각 0, 1, 2로 표현하기로 했다. 그리고 DP배열의 정의를 다음과 같이 해보자.
\(\small dp[k][y][x] =\) 좌표 (x, y)에서 k상태로 놓여지는 파이프의 경우의 수.
그럼, 위에서 발견했던 사실을 종합하여 다음과 같은 점화식을 생각해 볼 수 있다.
\[\small dp[0][y][x] = dp[0][y - 1][x] + dp[1][y - 1][x]\]
\[\small dp[1][y][x] = dp[0][y - 1][x-1] + dp[1][y - 1][x - 1] + dp[2][y - 1][x-1]\]
\[\small dp[2][y][x] = dp[1][y][x - 1] + dp[2][y][x - 1]\]
x와 y를 늘려가며 각 좌표마다 dp 배열값을 구하는 식으로 코드를 짜면, \(\scriptsize O(N ^ {2})\)에 문제를 해결할 수 있다. 나는 그 코드를 다음과 같이 짜 보았다.
vector<vector<vector<int>>> dp(3, vector<vector<int>>(N, vector<int>(N))); //dp[status][y][x]
dp[2][0][1] = 1; //base
for(int y = 0; y < N; ++y) {
for(int x = 0; x < N; ++x) {
for(int k = 0; k < 3; ++k) {
if(k == 0 && isNotWall(x, y) && isValid(x, y - 1))
dp[0][y][x] = dp[0][y - 1][x] + dp[1][y - 1][x] ;
else if(k == 1 && isNotWall(x, y) && isNotWall(x - 1, y) && isNotWall(x, y - 1) && isValid(x - 1, y - 1))
dp[1][y][x] = dp[0][y - 1][x-1] + dp[1][y - 1][x - 1] + dp[2][y - 1][x-1];
else if(k == 2 && isNotWall(x, y) && isValid(x - 1, y)) {
if(x == 1 && y == 0) continue; //skip base
dp[2][y][x] = dp[1][y][x - 1] + dp[2][y][x - 1];
}
}
}
}
코드를 보면 \(\scriptsize dp[2][0][1] = 1\)로 먼저 초기화하고 시작한다. 왜냐면, 시작이 (0, 1)에서 가로 상태로 시작하기 때문이다. 그 경우가 한가지 이므로 1로 초기화 해주고 y와 x를 순차적으로 늘려가며 각 상태에 대한 dp값들을 업데이트 한다(이때, k == 2에서 (1, 0)부분을 스킵하는데, 그게 기저 사례이기 때문에 스킵해준다..). isNotWall함수는 해당 좌표가 유효하고, 벽이 아닌지 체크하는 함수이고, isValid 함수는 해당 좌표가 유효한지 검사한다. 나는 이걸 대충 아래처럼 짰다.
bool isNotWall(int x, int y) {
if(x < 0 || x >= N || y < 0 || y >= N) return false;
if(map[y][x] == 1) return false;
else return true;
}
bool isValid(int x, int y) {
if(0 <= x && x < N && 0 <= y && y < N) return true;
else return false;
}
주목해서 봐야할 부분은 k == 1인 부분 즉, 대각 상태로 놓여진것을 계산하는 부분이다. 파이프가 놓여진 2 x 2 영역에는 벽이 없어야하고 좌표가 유효해야함을 유의하며 코드를 짜야 제대로 된 결과가 나온다.
이렇게 반복문을 모두 수행하고 나서, 답은 \(\scriptsize dp[0][N - 1][N - 1] + dp[1][N - 1][N - 1] + dp[2][N - 1][N - 1]\) 이므로 이것을 출력해주면 끝이다. 3차원 배열을 이용해 dp를 해보는것은 처음이었는데.. 하위 차원 dp랑 크게 다르진 않았다. 문제가 실수하기 좋은 요소를 포함하고 있기에 그걸 신경쓰는게 좀 까다로운 문제가 아니였을까?
코드 전문
17070 // 파이프 옮기기 1
21 Aug 2021
난이도
Gold IV
문제 풀이
예제 데이터를 보고 규칙을 추론해서 별을 찍는 문제이다. N = 24 일때의 데이터만 주어지는데 큰 블록으로 보면 3개의 삼각형이 하나의 큰 삼각형을 이루는 것을 쉽게 알 수 있다. 그리고 작은 삼각형 내부에도 또 다른 3개의 삼각형으로 그 삼각형을 이루고 있는걸 보면 재귀적인 구조로 이루어진다는 사실 또한 쉽게 캐치할 수 있다. 구조가 재귀적이니 풀이도 재귀함수를 사용하는 편이 편할 것이다. 먼저, 재귀함수를 만들기 전에 어떻게 그려야 할 지 생각을 해보도록 하자.
가장 작은 삼각형은 N = 3일때이다. 예제 데이터에서 잘 보면
이렇게 생긴 삼각형이 N = 3일때라는 것을 쉽게 파악 할 수 있을 것이다. 그렇기에, 재귀를 종료 시키는 N = 3이 되는 시점에는 저 삼각형을 넣어주고 함수를 종료시키면 된다. 그럼, 나머지는 어떻게 해야할까..? 잠시 그림을 보고 생각을 해보자.
가장 위에 있는 삼각형의 윗쪽 꼭지점 좌표를 \(\scriptsize (x, y)\)라고 해보자. 그럼, 좌측 아래 삼각형의 윗꼭지점 좌표는 \(\scriptsize (x - \frac {N} {2} , y + \frac {N} {2})\)이 된다. 우측 아래 삼각형 윗꼭지점 좌표는 \(\scriptsize (x + \frac {N} {2} , y + \frac {N} {2})\) 이렇게 된다. 즉, 어떤 삼각형이 주어지면 저렇게 좌표로 삼각형을 찢으면서 그려줄 수 있다. 삼각형을 그리는 함수를 \(\scriptsize f(N, x, y)\)라고 해보자. N은 삼각형의 크기이고 x, y는 각각 좌표이다. \(\scriptsize f(N, x, y)\)을 \(\scriptsize (x, y)\)에서 부터 시작하는 N 크기의 삼각형이라고 하면, 다음과 같은 점화식으로 표현 할 수 있다.
\[\scriptsize f(N, x, y) =
f(N / 2, x, y) +
f(N / 2, x - N / 2, y + N / 2) +
f(N / 2, x + N / 2, y + N / 2), (N \neq 3)\]
\(\scriptsize f(N, x, y) =\) 가장 작은 삼각형, \(\scriptsize (N = 3)\)
이렇게 점화식을 찾아내었으니, 이를 재귀함수로 작성해보자. 다음과 같이 짤 수 있겠다.
vector<vector<char>> baseTriangle =
{
{' ', ' ', '*', ' ', ' '},
{' ', '*', ' ', '*', ' '},
{'*', '*', '*', '*', '*'}
};
void solve(int N, int x, int y, vector<vector<char>>& map) {
if(N == 3) {
for(int i = 0; i < 3; ++i) {
for(int j = 0; j < 5; ++j) {
map[y + i][x - 2 + j] = baseTriangle[i][j];
}
}
return;
}
solve(N / 2, x, y, map);
solve(N / 2, x - N / 2, y + N / 2, map);
solve(N / 2, x + N / 2, y + N / 2, map);
}
먼저 N = 3일때의 삼각형을 미리 저장해두고, N = 3일때 해당 좌표에 그 문자들을 모두 대입하는 방식으로 짰다. N != 3일때는 위에서 찾아낸 점화식을 수행하도록 짠 것이다.
처음 함수를 호출 할때는 solve(N, N - 1, 0, map) 으로 호출하면 된다. (N - 1, 0)이 처음 시작 좌표이기 때문이다. 대체로 이런류의 문제는 점화식을 찾아내면 빨리 풀리는 듯 하다.
코드 전문
2448 // 별 찍기 - 11
20 Aug 2021
CCW (Counter - Clock - Wise)
CCW는 말 그대로 반시계 방향이라는 의미이다. CCW 알고리즘은 어떤 점들의 순서가 반시계방향으로 주어져 있는지 판별하는 알고리즘이다.
선분 \(\small \overline{AB}\)와 \(\small \overline{BC}\)가 이루는 각을 \(\small \theta\)라고 해보자. 그럼, \(\small \theta\)가 \(\small 0 \sim \pi\) 사이의 값을 가질 때, A - B - C가 이루는 방향이 반시계 방향임을 알 수 있다. 그러면, \(\scriptsize \overrightarrow{AB}\)와 \(\scriptsize \overrightarrow{BC}\)가 이루는 각을 생각해 보자. 이는, \(\small \pi\)에서 \(\small \theta\)를 뺀 값인 \(\small \pi - \theta\) 이다. \(\small \theta\)가 \(\small 0 \sim \pi\) 이면, \(\small \pi - \theta\)값 역시도 같은 범위에 속하므로, 두 벡터가 이루는 각을 살펴보아도 반시계 방향 판정이 가능하다.
그럼 그 각을 어떻게 알아낼 수 있을까? 벡터 간 연산에는 내적과 외적이 있었다. 내적은 \(\small \overrightarrow{a} \cdot \overrightarrow{b} = \mid a \mid \mid b \mid cos \theta\)로 정의 되므로, \(\small \theta\)에 대해 정리하면 각을 구할 수 있다. 그러나, 이 방법은 아크코사인값을 근사로 구해야하므로 오차가 실수 오차가 발생할 수 있을 뿐만 아니라 복잡하다. 더 쉬운 방법은 외적을 이용하는 방법이다.
외적의 크기는 \(\small \mid \overrightarrow{a} \times \overrightarrow{b}\mid = \mid a \mid \mid b \mid sin \theta\) 이다. 이때, 사인값은 \(\small 0 \sim \pi\) 사이의 각에서 양수값을 가진다. 즉, 두 벡터가 이루는 각에 대한 사인값이 양수값이라면 반시계 방향임을 훨씬 더 간단하게 알 수 있다. 정리하자면, 두 벡터간 외적값에 따라 방향을 결정할 수 있다는 것이다.
외적값이 양수라면 CCW를 의미하고, 0이라면 평행하므로 직선상에 점들이 존재하는 것이고, 음수라면 CW인 것이다. 이를 코드로 짠다면, 단순히 다음처럼 짤 수 있을 것이다.
typedef struct {
long long x;
long long y;
} Point;
int ccw(Point& v, Point& u) { //v vector and u vector
long long crossProduct = v.x * u.y - v.y * u.x;
if(crossProduct > 0) return 1;
else if(crossProduct < 0) return -1;
else return 0;
}
나는 벡터를 다루기 위해 구조체를 만들었고, ccw함수에선 두 벡터를 받아 외적을 계산한 후 부호에 따라 리턴해주면 된다.
이 알고리즘은 Convex Hull을 찾을 때도 사용되고, 어떤 점이 다각형 내부에 있는지 판정하는지에도 사용할 수 있다.
이걸로 풀 수 있는 가장 쉬운 문제는 백준 11758 CCW 문제이다. 문제 이름처럼 그냥 CCW를 구현하기만 하면 되는 매우 간단한 문제이다.