문제 이해 단계
입력으로 행(R)과 열(S)가 정수로 들어오고,
그다음에는 맵의 정보가 문자형으로 들어온다.
'. ' 은 공기, 'X'은 유성, '#'은 땅을 의미한다.
여기서 구하라고 하는 것은
X는 X끼리 모두 연결되어 있고 모양이 변하지 않는다고 가정하고,
위에서 아래로 수직으로 떨어진다.
이때, 최초로 유성이 땅에 닿는 시점의 모습을 나타내라는 것이다.
입력이 주어지는 가정은 다음 조건을 따른다.
1. 적어도 한 줄 이상의 공기('. ')가 주어진다.
2. 유성은 무조건 땅 위에서만 존재한다.
3. 유성은 공기 윗줄, 땅은 공기 아랫줄에만 위치한다.
4. R과 S의 범위는 3 ~ 3000 사이
해당 조건을 만족하면서 위를 구현하라는 문제.
문제 접근 단계
언뜻 보기에는 그래프 탐색 문제처럼 보이는데, 유성이 전부 연결되어 있다는 점을 주목해야 할 것 같다.
그 말은 땅에 떨어지더라도 형태를 유지해야 한다는 점.
일반적인 그래프 탐색으로 풀면 모든 X를 형태를 유지하면서
한 칸씩 내려주는 것을 최대 3000번을 해야 하는데,
이렇게 하면 시간초과가 뜰 것 같아서 다른 방법이 필요할 것 같았다.
어차피 형태를 유지해야 하기 때문에, 떨어질 수 있는 높이는 정해져 있다.
한 열에서 땅과 유성의 거리차가 가장 작은 거리를 이동거리로 선택하는 것을 방법으로 선택했다.
어차피 높이가 남아도 땅에 닿아버렸기 때문에 더 이상 움직이지 못할 것이기 때문.
위 그림을 보면 어느 정도 이해가 될 것이다.
해당 방식을 사용하기 위해 각 열끼리 묶어 S개의 열을 만든 뒤, 각 열에 대한 거리를 구해준다.
그리고 새롭게 그림을 그려주는 것 또한 각 열끼리 처리하는 것으로 한다.
여기서 약간의 BFS가 들어가는데, 유성과 땅은 수직으로만 상호작용한다.
그렇기 때문에 땅이 유성을 찾기 위해서는 위쪽방향으로,
유성이 땅을 찾기 위해서는 아래쪽 방향으로 탐색하는 것으로 찾는다.
그림을 새로 그려주는 방법은 다음과 같이 진행된다.
1.
각 열에서 땅에 가장 높은 지점을 찾는다.
2.
한 칸씩 수직으로 올라가면서 'X'를 찾는다.
(최초로 찾는 X가 가장 낮은 X)
3.
그 좌표를 '. ' 으로 바꾸고
구한 최소 이동거리만큼 아래로 이동시킨다.
4.
한 칸 위로 올라가서 'X'가 있는지 확인한다.
있다면 똑같이 3~4번을 반복한다.
5.
끝까지 도달하거나 'X'가 없을 때까지 반복한다.
해당 방법을 반복하면서 구할 수 있다.
근데 이 문제는 뉘앙스의 문제인지는 모르겠는데 예외적인 케이스가 있다.
아래와 같은 케이스이다.
5 5
..X..
.....
....#
....#
..###이런 식으로 어떤 열에 아예 땅이 없거나, 땅은 있는데 유성이 없을 수가 있다.
그래서 코드로 구현할 때 이 점을 유의해가면서 코드를 구현해줘야 한다.
문제 구현 단계
int R,S; // 행,렬
char map[3001][3001]; // 전체 맵
// (sx,sy)에서 시작할 때 거리 구하기
int getDistance(int sx, int sy){
if(sx > R) return 9999; // 시작 값이 잘못되면 해당 count 나오지않게
queue<pair<int,int>> q;
int count = 0; // 횟수
q.push(make_pair(sx,sy));
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
if(x-1 < 1) return 9999; // 한칸 위로
if(map[x-1][y] != '.') continue; // '.' 일때만 계속
count++;
q.push(make_pair(x-1,y));
}
return count;
}땅의 좌표 (sx, sy)에서 시작했을 때의 유성과의 거리차를 구하는 함수이다.
여기서 if(sx > R)은 만약 해당 열에 #이 없으면 그 열의 sx는 9999로 초기화되게 설정해 놨다.
그래서 해당 의미는 해당 열에 #이 없는 경우에는 제외하는 것이다.
나머지는 BFS를 사용해 한 칸씩 올라가 주면서 '.'이 나올 때마다 count++해주면서
'.'이 없거나 끝까지 갔을 때까지 반복하여 count를 반환하도록 한다.
여기서 if(x-1 < 1) return 9999; 는 예외처리를 해주는 것이다.
만약 x-1 < 1이 나왔다는 것은 맵 밖으로 나갔다는 것인데,
이게 나올 수 있는 경우는 해당 열에 'X'가 없는 경우밖에 없다.
그러니 이 경우도 제외해 준다.
// 유성을 k만큼 아래로 떨어뜨림
void drop(int k,vector<int> groundTop){
for(int i = 1; i <= groundTop.size(); i++){
int x = groundTop[i];
int y = i;
queue<pair<int,int>> q;
q.push(make_pair(x,y));
while(!q.empty()){
int nx = q.front().first -1;
int ny = q.front().second;
q.pop();
if(nx > R || nx < 1) continue;
if(map[nx][ny] == 'X'){
map[nx+k][ny] = 'X'; // k만큼 이동
map[nx][ny] = '.'; // 해당 자리 .으로 초기화
}
q.push(make_pair(nx,ny));
}
}
}최소 이동거리를 k라고 하고, 이 k를 이용하여 유성을 떨어뜨리는 함수이다.
첫 번째 열부터 마지막열까지 반복해 준다.
이 때는 아래로 떨어지는 것이기 때문에 k만큼 떨어지는 것이기 때문에 nx - k를 해준다.
이미 진행했던 것을 삭제하는 것을 방지하기 위해 가장 아래부터 시작하여 점점 위로 올라간다.
(nx = x - 1 인 이유)이 행위를 다음 칸이 'X'면 계속한다.
이 것도 BFS를 베이스로 하여 코드를 짰다.
이제 아래에 전체코드에 대한 설명을 조금 하고 끝마치겠다.
#include <iostream>
#include <queue>
#include <vector>
#include <utility>
using namespace std;
int R,S; // 행,렬
char map[3001][3001]; // 전체 맵
// (sx,sy)에서 시작할 때 거리 구하기
int getDistance(int sx, int sy){
if(sx > R) return 9999; // 시작 값이 잘못되면 해당 count 나오지않게
queue<pair<int,int>> q;
int count = 0; // 횟수
q.push(make_pair(sx,sy));
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
if(x-1 < 1) return 9999; // 한칸 위로
if(map[x-1][y] != '.') continue; // '.' 일때만 계속
count++;
q.push(make_pair(x-1,y));
}
return count;
}
// 유성을 k만큼 아래로 떨어뜨림
void drop(int k,vector<int> groundTop){
for(int i = 1; i <= groundTop.size(); i++){
int x = groundTop[i];
int y = i;
queue<pair<int,int>> q;
q.push(make_pair(x,y));
while(!q.empty()){
int nx = q.front().first -1;
int ny = q.front().second;
q.pop();
if(nx > R || nx < 1) continue;
if(map[nx][ny] == 'X'){
map[nx+k][ny] = 'X'; // k만큼 이동
map[nx][ny] = '.'; // 해당 자리 .으로 초기화
}
q.push(make_pair(nx,ny));
}
}
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> R >> S;
vector<int> groundTop(S+1,9999);
for(int i = 0; i < R; i++){
string str;
cin >> str;
for(int j = 0; j < str.length(); j++){
map[i+1][j+1] = str[j];
if(str[j] == '#') {
// 각 열의 최대 땅 높이
groundTop[j+1] = min(groundTop[j+1],i+1);
}
}
}
int distance = 9999;
for(int i = 1; i <= S; i++){
distance = min(distance,getDistance(groundTop[i],i)); // 최소 이동거리
}
if(distance > 0) drop(distance,groundTop); // 이동거리가 0일때는 제외
for(int i = 1; i <= R; i++){
for(int j = 1; j <= S; j++) cout << map[i][j];
cout << "\n";
}
}인덱스를 1부터 시작해 주기 위해 i+1, j+1을 해주었고, 처음 입력을 받아줄 때 바로 땅의 최대 높이를 받아줬다.
그리고 distance를 계산하고 이 값이 0이라는 것은 움직일 필요가 없다는 뜻이므로
그냥 원래의 맵을 출력 하도록 했다.
나머지는 위에 설명한 그대로이다.
시행착오
실버 2 문제치고는 좀 많이 어려웠던 것 같다.
반례도 구하기 어려웠고 구현도 그렇게 쉽지 않았다.
내가 국어가 딸리는 건지 모르겠는데, 솔직히 좀 억까당한 느낌인데..