BOJ 1175

배달

문제출처

문제 해석

  • 민식이가 선물을 모두 배달하기 위한 최소거리를 구하는 문제입니다.
  • 선물을 배달해야하는 곳(C)는 두 군데 있습니다.

설계(X)

  • bfs로 구현이 가능한 문제입니다.
  • 멍멍멍님의 블로그에서 두개의 C중 하나를 다른 문자로 변경함으로써, 두 개를 구분하는 아이디어를 얻었습니다.
  • 두번 연속으로 같은 방향을 이동하면 안되므로, 이전에 이동한 방향에 대한 정보 또한 큐에 추가하도록 합니다.
  • dist[x][y][방향][첫번째 C 방문여부][두번째 C 방문여부]를 이용하여 두개의 C를 모두 방문하도록 하였습니다.

구현(30)

코드
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321
#define MAXN 50

char map[MAXN][MAXN];
struct node{
    int x;
    int y;
    int dir;
    bool flag1;
    bool flag2;
};
int dist[MAXN][MAXN][4][2][2];
int N,M;
queue<node> q;
pair<int,int> s;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
bool flag[2];
int bfs(){
    q.push({s.first,s.second,-1});
    int ans = 0;
    while (!q.empty()){
        int x=  q.front().x;
        int y = q.front().y;
        int cur_dir = q.front().dir;
        bool flag1 = q.front().flag1;
        bool flag2 = q.front().flag2;
        int cur_dist;
        if (cur_dir!=-1){
            cur_dist = dist[x][y][cur_dir][flag1][flag2];
        }
        if (flag1 && flag2) return dist[x][y][cur_dir][flag1][flag2];
        q.pop();
        for (int k = 0; k < 4; k++){
            if (cur_dir != -1 && cur_dir == k) continue;
            int nx = x + dx[k];
            int ny = y + dy[k];
            bool n_flag1 = flag1;
            bool n_flag2 = flag2;
            if (nx < 0 || ny < 0 || nx>=N || ny>=M) continue;
            if (dist[nx][ny][k][flag1][flag2] != -1 || map[nx][ny] == '#') continue;
            if (map[nx][ny] == 'K'){
                n_flag1 = true;
            }
            else if (map[nx][ny] == 'C') n_flag2 = true;
            if (cur_dir == -1) dist[nx][ny][k][n_flag1][n_flag2] = 1;

            else dist[nx][ny][k][n_flag1][n_flag2] = cur_dist + 1;
            q.push({nx,ny,k,n_flag1,n_flag2});
        }
    }
    return -1;
}
int main(){
    bool b = false;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    memset(dist,-1,sizeof(dist));
    for (int i = 0 ;i <N; i++){
        for (int j = 0;j <M;j++){
            cin >> map[i][j];
            if (map[i][j] == 'C'){
                if (!b) {
                    b = true;
                    map[i][j] = 'K';
                }
            }
            else if (map[i][j] == 'S'){
                s = {i,j};
            }
        }
    }
    cout << bfs() <<"\n";
    return 0;

}
디버깅
  • 기존에 둘중에 하나의 선물에 도착할 경우 방문표시를 해주고, 모든 큐를 지워서 다른 선물에 도착하기까지의 거리를 추가한 결과를 출력하도록 하였습니다.
  • 그러나, WA를 받아 반례를 찾지 못해 다른 아이디어를 이용하여 구현하였습니다.
제출결과
  • 0ms

마무리

  • dp또는 bfs를 이용하여 해결할 수 있는 문제였습니다. 생각을 깊게 하지 않아서 정확하게 구현하지 못했습니다.