| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 6319 | 1659 | 1039 | 24.202% |
문제
창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.
동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.
창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.
막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.
미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.
동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)
다음 R개 줄에는 C개의 문자가 주어지며, '.'는 빈 칸, 'x'는 미네랄을 나타낸다.
다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)
마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다. 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다. 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.
공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.
출력
입력 형식과 같은 형식으로 미네랄 모양을 출력한다.
접근
전형적인 DFS 문제라고 판단했으나 생각보다 까다로운 부분이 많다.
미네랄 하나가 없어질 때 클러스터를 어떻게 처리하냐가 핵심이다.
나는 처음에 왼쪽, 위, 오른쪽만 보면서 DFS를 돌려 많은 시간을 날렸다.
o x x
xㅤx
ㅤ x
대충 이렇게 생겨서 o가 부숴지면 아래에도 클러스터가 생길수도 있었다.
클러스터를 찾으면, 몇 칸 떨어지는지를 구해야되는데 여기에도 함정이 있다.
아래로 순회할 때, 현재 클러스터에 포함된 미네랄은 제외해야한다는 점이다.
쉬운 문제인줄 알고 대충 풀었는데 생각보다 신경쓸 것이 많았다.
모든 문제를 열심히 집중해서 푸는 습관을 들이자..
풀이
왼쪽 오른쪽 구분해서 순회하는데, 미네랄이 있으면 바로 제거해준다.
그 후 4방향으로 DFS를 진행해서 클러스터를 찾는다.
y == 1 인 경우가 있으면 클러스터가 아니라서 flag로 처리했다.
클러스터가 있다면 find_height를 통해 떨어트릴 높이를 찾는다.
아래에 visited된 미네랄이 있다면, 바로 넘어갔다.
그 이후에는 하나하나 순회하면서 떨어트리고 삭제하는 것이 아니라,
떨어트린 좌표를 한번에 저장해놓고 마지막에 추가해야 된다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { -1, 0, 1, 0 };
int R, C, N, height;
char arr[101][101];
bool visited[101][101];
bool isLeft = false, flag;
vector<pair<int, int>> v;
void DFS(int y, int x)
{
visited[y][x] = true;
v.push_back({ y, x });
if (y == 1) flag = true;
FUP(i, 0, 3)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 1 || nx < 1 || ny > R || nx > C || arr[ny][nx] == '.' || visited[ny][nx]) continue;
DFS(ny, nx);
}
}
void find_height(int y, int x)
{
int tmp = y - 1;
FDOWN(i, y - 1, 1)
{
if (visited[i][x])
{
tmp = 1000;
break;
}
if (arr[i][x] == 'x')
{
tmp = y - i - 1;
break;
}
}
height = min(height, tmp);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN2(R, C);
FDOWN(i, R, 1)
{
FUP(j, 1, C)
{
CIN(arr[i][j]);
}
}
CIN(N);
while (N--)
{
int x = -1, y;
isLeft = !isLeft;
CIN(y);
if (isLeft)
{
FUP(i, 1, C)
{
if (arr[y][i] == 'x')
{
x = i;
break;
}
}
}
else
{
FDOWN(i, C, 1)
{
if (arr[y][i] == 'x')
{
x = i;
break;
}
}
}
if (x == -1) continue;
arr[y][x] = '.';
FUP(i, 0, 3)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (arr[ny][nx] == 'x')
{
v.clear();
MS(visited, false);
flag = false;
DFS(ny, nx);
if (flag) continue;
height = 1000;
for (auto p : v)
{
find_height(p.first, p.second);
}
vector<pair<int, int>> tmp;
for (auto p : v)
{
arr[p.first][p.second] = '.';
tmp.push_back({ p.first - height, p.second });
}
for (auto p : tmp)
{
arr[p.first][p.second] = 'x';
}
}
}
}
FDOWN(i, R, 1)
{
FUP(j, 1, C)
{
COUT(arr[i][j]);
}
ENDL;
}
return 0;
}