백준(BOJ) 2933번 미네랄
문제 : https://www.acmicpc.net/problem/2933
창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.
동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.
창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.
막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.
미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.
동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.
풀이 :
막대를 하나씩 던질때마다 DFS를 통해 한번에 이동할 미네랄들을 group에 저장한다.
그리고 low 배열을 만들어서 각 열마다 가장 큰 행을 넣어주자. 즉 가장 밑에있는 미네랄을 넣어주는 것.
그리고 각 열마다 가장 큰 행들이 얼마나 밑으로 내려갈수 있는지 정한다. 그 후 그중 최소만큼 옮긴다.
막대를 던진 횟수 만큼 반복한다.
코드 ( C++ )
| #include <iostream> | |
| #include <vector> | |
| #include <algorithm> | |
| #include <cstring> | |
| using namespace std; | |
| char cave[100][100]; | |
| int branch[100]; | |
| int N; | |
| int R, C; | |
| int visited[100][100]; | |
| const int dy[4] = { 1,-1,0,0 }; | |
| const int dx[4] = { 0,0,1,-1 }; | |
| vector<pair<int, int>> group; | |
| void DFS(int y, int x) | |
| { | |
| if (cave[y][x] == '.') return; | |
| if (visited[y][x]) return; | |
| visited[y][x] = true; | |
| group.push_back({ y,x }); | |
| for (int i = 0; i < 4; ++i) | |
| { | |
| int ny = y + dy[i]; | |
| int nx = x + dx[i]; | |
| if (0 <= nx && nx < C && 0 <= ny && ny < R) | |
| DFS(ny, nx); | |
| } | |
| } | |
| void solve() | |
| { | |
| memset(visited, 0, sizeof(visited)); | |
| for (int a = 0; a < R; ++a) | |
| for (int b = 0; b < C; ++b) | |
| { | |
| if (visited[a][b]) continue; | |
| if (cave[a][b] == '.') continue; | |
| group.clear(); | |
| DFS(a, b); | |
| vector<int> low(C, -1); | |
| for (int i = 0; i < group.size(); ++i) | |
| { | |
| auto &p = group[i]; | |
| //각 열마다 가장 밑에있는 행을 찾는다 | |
| low[p.second] = max(low[p.second], p.first); | |
| //옮길점들 이므로 '.'로 바꿔주자 | |
| cave[p.first][p.second] = '.'; | |
| } | |
| //얼마나 밑으로 옮길지 결정 | |
| int lowmove = R; | |
| for (int i, j = 0; j < C; ++j) { | |
| if (low[j] == -1) continue; | |
| i = low[j]; | |
| // 내려갈수 있을때까지 내려간다 | |
| while (i < R && cave[i][j] == '.') { | |
| ++i; | |
| } | |
| lowmove = min(lowmove, i - low[j] - 1); | |
| } | |
| for (int i = 0; i < group.size(); ++i) { | |
| auto &p = group[i]; | |
| p.first += lowmove; | |
| cave[p.first][p.second] = 'x'; | |
| visited[p.first][p.second] = true; | |
| } | |
| } | |
| } | |
| int main() | |
| { | |
| ios_base::sync_with_stdio(false); | |
| cin.tie(0); | |
| cin >> R >> C; | |
| for (int i = 0; i < R; ++i) | |
| for (int j = 0; j < C; ++j) | |
| { | |
| cin >> cave[i][j]; | |
| } | |
| cin >> N; | |
| for (int i = 0; i < N; ++i) | |
| { | |
| int num; | |
| cin >> num; | |
| branch[i] = R - num; | |
| } | |
| // 한번 맞치고 한번 DFS 검사 | |
| for (int i = 0; i < N; ++i) | |
| { | |
| int height = branch[i]; | |
| if (i % 2 == 0) | |
| { | |
| for (int j = 0; j < C; ++j) | |
| { | |
| if (cave[height][j] == 'x') { | |
| cave[height][j] = '.'; | |
| break; | |
| } | |
| } | |
| } | |
| else | |
| { | |
| for (int j = C - 1; j >= 0; --j) | |
| { | |
| if (cave[height][j] == 'x') { | |
| cave[height][j] = '.'; | |
| break; | |
| } | |
| } | |
| } | |
| // DFS 검사 | |
| solve(); | |
| } | |
| //cave 출력 | |
| for (int i = 0; i < R; ++i) { | |
| for (int j = 0; j < C; ++j) | |
| cout << cave[i][j]; | |
| cout << "\n"; | |
| } | |
| return 0; | |
| } |
