Compy's Blog
496 words
2 minutes
[BOJ] 배달
2025-09-24

배달

TimeLimitMemoryLimitConditionTAG
2s128MB(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.
 .#...#.#.
 
 
 */
[BOJ] 배달
https://compy07.github.io/Blog/posts/boj/1175/
Author
뒹굴뒹굴 이정훈 공부방
Published at
2025-09-24