| TimeLimit | MemoryLimit | Condition | TAG |
|---|---|---|---|
| 1s | 256MB | (1<= R, C <= 1500) | BFS(너비우선탐색), Implementation(구현) |
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
아래에는 세 가지 예가 있다.
…XXXXXX..XX.XXX …XXXX…XX …XX… …XXXXXXXXX.XXX …XXXX..X… …X… …XXXXXXXXXXXX.. …XXX..XXXX… …X…X… ..XXXXX..XXXXXX.. …XXX…XXXX… …X…XX… .XXXXXX..XXXXXX.. ..XXXX…XXXX… …XX…XX… XXXXXXX…XXXX… ..XXXX…XX… …X… ..XXXXX…XXX… …XX…X… … …XXXXX.XXX… …XX…X… …처음 첫째 날 둘째 날 백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.
처음은 되게 간단하게 bfs 한번만 돌려서, 대충 계산으로 해결하려고 했다가 군데 군데 뚫려있는 ’.’이 있으면 성립이 안되는 경우가 발생
노선을 틀어서 먼저 각 빙하마다 시간이 얼마나 지나야 녹는지를 선행적으로 구함. 이후에 여기에서 BFS를 전체적으로 돌면서 백조와 백조끼리의 제일 빠르게 갈 수 있는 cost를 탐색하고 반환한다.
이러한 로직을 따랐습니다.
모두 즐거운 PS 되세요!!
정답 코드
다른 분들이 하시는거 보면 엄청 간단하고 효율적으로 풀이하셨던데… ㄷㄷ
아직도 제 실력이 많이 부족한가 봅니다.
더 열심히 해야겠습니다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int r, c;
char board[1501][1501];
int visited[1501][1501];
int visited_[1501][1501];
const int MAX = 1000000007;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
struct pos{
int cost;
int y, x;
};
struct compare {
bool operator()(const pos& p1, const pos& p2) {
return p1.cost > p2.cost;
}
};
void solution(){
queue<pos> q;
for(int i = 0; i < r; i ++){
for(int j = 0; j < c; j++){
if(board[i][j] != 'X') q.push({0, i, j});
}
}
while(!q.empty()){
auto [cost, y, x] = q.front(); q.pop();
if(visited[y][x] <= cost) continue;
visited[y][x] = cost;
for(int i = 0; i < 4; i++){
int ny = y + dy[i], nx = x + dx[i];
if(0 <= ny && ny < r && 0 <= nx && nx < c && visited[ny][nx] > cost+(board[ny][nx] == 'X')){
if(board[ny][nx] != 'X') q.push({0, ny, nx});
else q.push({cost+(board[ny][nx] == 'X'), ny, nx});
}
}
}
}
int main(){
cin >> r >> c;
priority_queue<pos, vector<pos>, compare> q;
pair<int, int> target;
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
cin >> board[i][j];
if(board[i][j] == 'L'){
if(q.empty()) q.push({0, i, j});
else target = {i, j};
}
visited[i][j] = MAX;
visited_[i][j] = MAX;
}
}
solution();
while(!q.empty()){
auto [cost, y, x] = q.top(); q.pop();
if(visited_[y][x] <= cost) continue;
visited_[y][x] = cost;
cost = max(visited[y][x], cost);
for(int i = 0; i < 4; i++){
int ny = y + dy[i], nx = x + dx[i];
if(0 <= ny && ny < r && 0 <= nx && nx < c && visited_[ny][nx] > cost){
q.push({cost, ny, nx});
}
}
}
//
//
// for(int i = 0; i < r; i++){
// for(int j = 0; j < c; j++){
// cout << visited_[i][j] << " ";
// }
// cout << "\n";
// }
cout << visited_[target.first][target.second];
return 0;
}