문제
창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.
동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.
창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.
막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.
미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.
동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)
다음 R개 줄에는 C개의 문자가 주어지며, '.'는 빈 칸, 'x'는 미네랄을 나타낸다.
다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)
마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다. 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다. 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.
공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.
5 6
......
..xx..
..x...
..xx..
.xxxx.
1
3
이러한 형태의 문제가 가장 요즘 코딩테스트 트렌드가 아닌가 싶다. (그래프 중에서)
어려운 알고리즘이기 보다는 말을 그대로 구현해낼 수 있는 능력을 보는 문제
백조의 호수 문제처럼 컨트롤 해야하는 객체가 많은 것도 아니고, 미네랄 X만 컨드롤 하면 된다.(클러스터는 단일이 아니라 상하좌우로 같이 붙어서 이동한다.)
- 왼쪽/오른쪽 한번씩 던져서 미네랄을 깬다.
- 공중에 떠있는 클러스터를 찾는다.
- 바닥까지 떨어 뜨리거나, 떨어지는 중간에 X를 만나면 거기까지만 떨어뜨린다.
크게는 이렇게 구현하면 된다. 위 순서대로 알아보자
- 왼쪽 / 오른쪽 한번씩 던져서 미네랄을 깬다.
1.1 호출 방식의 bool 형태를 파라미터로 넘겨서 true/false 로 나누어 계산한다.
1.2 board를 왼쪽부터 시작 for(int i = 0; i <c; i++)
board를 오른쪽부터 시작 for(int i = c-1; i>= 0; i--)
이렇게 해서 처음 만나는 'X'를 만나면 break
여기까지는 크게 어렵지 않고 쉽고 빠르게 할 수 있다. 왼쪽/오른쪽 방향의 시작도 크게 어렵게 생각하지 않고 단순하게 생각하는게 좋다. 코드의 가독성을 좋게 char 'L' or 'R' 방식으로 하는 것도 좋다.
if ( i % 2 == 0 ) start = true;
else start = false;
if (!removeIce(start, throw_hieght) ) continue; // 안지워졌으면 다시 그릴필요도 없다.bool removeIce(bool start, int _height)
{
bool bret = false;
if( start == true) // 왼쪽 부터
{
for(int i = 0; i <c; i++)
{
if(board[_height-1][i] =='x')
{
board[_height-1][i] = '.';
bret = true;
break;
}
}
}
else // 오른쪽 부터
{
for(int i = c-1; i>= 0; i--)
{
if(board[_height][i] =='x')
{
board[_height-1][i] = '.';
bret = true;
break;
}
}
}
return bret;
}
- 공중에 떠있는 클러스터를 찾는다.
공중에 떠있는 클러스는 어떻게 찾을 수 있을까? 클러스터는 단일 'X' 모양이 아니라 X를 기준으로 상하좌우 미네랄이 존재하면 그 미네랄들을 묶어서 클러스터라고 한다. 그렇다면 맨 마지막 줄에서만 BFS 탐색을 한다면, 방문되지 않는 미네랄들이 클러스터 라고 생각할 수 있다.
......
...xxx
..x...
..xx..
.xxxx.
이런 모양이라면 진한 xxx 방문될 수 없으므로 떨어져야 하는 클러스터라고 생각할 수 있다.
즉, 공중에 떠있는 클러스터다.
bool changeboard()
{
bool bret = false;
for(int i = 0 ; i<c; i++)
{
if(board[r-1][i] =='x' && board[r-1][i] == false)
{
BFS(r-1, i); // 맨 마지막 (r-1) , 첫번째 줄만 BFS 탐색을 한다.
}
}
}void BFS(int x, int y)
{
std::queue<std::pair<int, int> > q;
q.push(std::make_pair(x,y));
visited[x][y] = true;
while (!q.empty())
{
int _x = q.front().first;
int _y = q.front().second;
q.pop();
for(int i = 0; i < 4; i++)
{
int nx = _x + dx[i];
int ny = _y + dy[i];
if(nx <0 || nx >=r || ny <0 || ny >= c) continue;
if (board[nx][ny] == 'x' && visited[nx][ny] == false)
{
visited[nx][ny] = true;
q.push(std::make_pair(nx,ny));
}
}
}
}- 바닥까지 떨어 뜨리거나, 떨어지는 중간에 X를 만나면 거기까지만 떨어뜨린다.
이제 전역변수로 선언 해놓은 방문 배열중에 'X'면서 방문 되지 않은 클러스터를 대상으로 떨어 뜨릴 준비를 한다.
for(int i = 0; i<r; i++)
{
for(int j = 0; j<c; j++)
{
if(board[i][j] == 'x' && visited[i][j] == false)
{
bret = true;
air_q.push_back(std::make_pair(i,j));
visited2[i][j] = true;
}
}
}공중에 떠있는 좌표들을 모아서 vector에 푸시를 먼저 해주고 떨어져야하는 최소 높이를 구한다.
......
...xxx
..x...
..xx..
.xxxx.
이렇게 된 클러스터는 사실상 각 미네랄마다 떨어질 수 있는 높이가 다르다.(최소 1만큼만 떨어질 수 있다)
만약에 떨어질때 'X'를 만나면 멈춰야하지만 혹시나 그 미네랄 또한 떨어져야하는 미네랄이라면 떨어지는데 영향을 줄 수 없다.
int max_height(int x, int y)
{
int h = 0;
for(int i = x+1; i<r; i++)
{
if (board[i][y] == 'x')
{
if (visited2[i][y] == true) return INF;
else return h;
}
else if (board[i][y] == '.') h++;
}
return h;
}
void redrawboard()
{
int high_h= INF-1;
for(int i = 0; i<air_q.size(); i++)
{
int x = air_q[i].first;
int y = air_q[i].second;
int temp_h = max_height(x,y);
if(temp_h == INF) continue;
else high_h = std::min(high_h, temp_h);
}
두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다 (공중에 떠 있는 클러스터는 1개 뿐이라는 소리와 같다)
std::sort(air_q.begin(), air_q.end());
for(int i = air_q.size() -1; i>=0; i--)
{
int x = air_q[i].first;
int y = air_q[i].second;
board[x][y] = '.';
board[x+high_h][y] ='x';
//std::cout<<x+ high_h <<std::endl;
}
}
전체코드
#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321
int r,c;
char board[101][101];
bool visited[101][101];
bool visited2[101][101];
int n;
int dx[] = {1,0,-1, 0};
int dy[] = {0,1,0,-1};
std::vector<int> v_height;
std::vector<std::pair<int,int> > air_q;
bool removeIce(bool start, int _height)
{
bool bret = false;
if( start == true) // 왼쪽 부터
{
for(int i = 0; i <c; i++)
{
if(board[_height-1][i] =='x')
{
board[_height-1][i] = '.';
bret = true;
break;
}
}
}
else // 오른쪽 부터
{
for(int i = c-1; i>= 0; i--)
{
if(board[_height][i] =='x')
{
board[_height-1][i] = '.';
bret = true;
break;
}
}
}
return bret;
}
void input()
{
std::cin>>r>>c;
for (int i = 0; i<r; i++)
{
for(int j = 0; j<c; j++)
{
std::cin>>board[i][j];
}
}
std::cin>>n;
for(int i = 0; i<n; i++)
{
int temp;
std::cin>>temp;
v_height.push_back(temp);
}
}
void BFS(int x, int y)
{
std::queue<std::pair<int, int> > q;
q.push(std::make_pair(x,y));
visited[x][y] = true;
while (!q.empty())
{
int _x = q.front().first;
int _y = q.front().second;
q.pop();
for(int i = 0; i < 4; i++)
{
int nx = _x + dx[i];
int ny = _y + dy[i];
if(nx <0 || nx >=r || ny <0 || ny >= c) continue;
if (board[nx][ny] == 'x' && visited[nx][ny] == false)
{
visited[nx][ny] = true;
q.push(std::make_pair(nx,ny));
}
}
}
}
bool changeboard()
{
bool bret = false;
for(int i = 0 ; i<c; i++)
{
if(board[r-1][i] =='x' && board[r-1][i] == false)
{
BFS(r-1, i);
}
}
memset(visited2, 0, sizeof(visited2));
for(int i = 0; i<r; i++)
{
for(int j = 0; j<c; j++)
{
if(board[i][j] == 'x' && visited[i][j] == false)
{
bret = true;
air_q.push_back(std::make_pair(i,j));
visited2[i][j] = true;
}
}
}
return bret;
}
int max_height(int x, int y)
{
int h = 0;
for(int i = x+1; i<r; i++)
{
if (board[i][y] == 'x')
{
if (visited2[i][y] == true) return INF;
else return h;
}
else if (board[i][y] == '.') h++;
}
return h;
}
void redrawboard()
{
int high_h= INF-1;
for(int i = 0; i<air_q.size(); i++)
{
int x = air_q[i].first;
int y = air_q[i].second;
int temp_h = max_height(x,y);
if(temp_h == INF) continue;
else high_h = std::min(high_h, temp_h);
}
std::sort(air_q.begin(), air_q.end());
for(int i = air_q.size() -1; i>=0; i--)
{
int x = air_q[i].first;
int y = air_q[i].second;
board[x][y] = '.';
board[x+high_h][y] ='x';
//std::cout<<x+ high_h <<std::endl;
}
}
int main()
{
input();
bool start = false;
for(int i = 0; i<v_height.size(); i++)
{
memset(visited, 0, sizeof(visited));
memset(visited2, 0, sizeof(visited2));
air_q.clear();
int throw_hieght = v_height[i];
if ( i % 2 == 0 ) start = true;
else start = false;
if (!removeIce(start, throw_hieght) ) continue; // 안지워졌으면 다시 그릴필요도 없다.
if (!changeboard()) continue;
else redrawboard();
//BFS();
for(int i= 0; i<r; i++)
{
for(int j = 0; j <c; j++)
{
std::cout<<board[i][j];
}
std::cout<<std::endl;
}
}
return 0;
}