496 words
2 minutes
[BOJ] 배달
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
2s | 128MB | (1 ≤ N, M ≤ 50) | BFS |
간단한 BFS 문제이고, 조금 특이한 점은 각 방향에 대해서 visited 처리 정도가 있겠습니다.
저는 조금 비효율적으로 작성했는데.. 학교에서 간단히 풀다 보니 일단 풀자라는 마인드로 구현해서 저렇게 되었구요..
조금 더 생각해보면 훨씬 효율적인 풀이가 가능할 듯 합니다.. 한번 BFS 변형 문제 연습으로 풀어보면 좋을 것 같네요.
정답 코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
using namespace std;
using ll = long long;
int n, m;
char board[101][101];
int visited[101][101][4][3];
vector<pair<int, int>> cs;
struct info {
pair<int, int> pos;
int cost;
int getCost;
int visited;
int dir;
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
pair<int, int> start;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
char tmp;
cin >> tmp;
if(tmp == 'S') {
start = {i, j};
board[i][j] = '.';
}
else if(tmp == 'C'){
cs.push_back({i, j});
}
else{
board[i][j] = tmp;
}
for(int k = 0; k < 4; k++){
visited[i][j][k][0] = 1000000000;
visited[i][j][k][1] = 1000000000;
visited[i][j][k][2] = 1000000000;
}
// visited[i][j][2] = 1000000000;
}
}
// visited[start.first][start.second][0] = 0;
queue<info> q;
q.push({start, 0, 0, 0, -1});
int result = 1000000000;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
while(!q.empty()){
info information = q.front(); q.pop();
for(int i = 0; i < 4; i++){
if(information.dir == i) continue;
int nx = information.pos.second + dx[i];
int ny = information.pos.first + dy[i];
if(0 < ny && ny <= n &&
0 < nx && nx <= m && board[ny][nx] != '#'){
int currentGet = information.getCost;
int currentIdx = information.visited;
for(int idx = 0; idx < cs.size(); idx++){
if(cs[idx].first == ny && cs[idx].second == nx){
currentIdx = idx+1;
if(idx+1 != information.visited){
currentGet++;
break;
}
}
}
// cout << ny << " " << nx << " " << currentGet << "\n";
if(currentGet == 2){
result = min(result, information.cost + 1);
continue;
}
if(visited[ny][nx][i][currentIdx] > information.cost + 1) {
visited[ny][nx][i][currentIdx] = information.cost + 1;
q.push({{ny, nx}, information.cost + 1, currentGet, currentIdx, i});
}
}
}
}
//
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= m; j++){
// cout << visited[i][j][1][1] << " ";
//// result = min({visited[i][j][0][2], visited[i][j][1][2],
//// visited[i][j][2][2], visited[i][j][3][2], result});
// }
// cout << "\n";
// }
if(result == 1000000000) cout << -1;
else cout << result;
return 0;
}
/*
3 9
...#..##.
C...S..C.
.#...#.#.
*/