글 읽기 - 로봇은 멈추지 않나요?

tjdgnsqn3 2달 전 0

예를들어 100개 분열을 시작하자 하면 매 단위시간마다 100이 늘어나는 걸까요?

tjdgnsqn3 2달 전 1

우선순위 큐와 bfs를 통해 열쇠 위치에 도착했을 때, 0으로 갱신하면 왜 정답이 안 되는지도 알 수 있을까요?

1. 시작점에서 무한개의 로봇을 뿌렸다고 가정

2. 첫 열쇠에 도착하는 로봇은 (1) 로부터 왔을 것임

3. 2번째는 첫 열쇠로부터 가까우면 첫 열쇠에서 왔을 것이고, (1)에서 왔을 거임

4. n번째는 1~n-1에서 가까운 로봇이 도착했을 것이다.

멈춘다면 위 단계가 성립하는거 같은데, 문득 멈추지 않는건가 싶어서요.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node {
    int x,y, c;
};

struct Compare {
    bool operator()(const Node &a, const Node &b) {
        return a.c > b.c;
    }
};

void solve(){
    int N, K; cin >> N >>K;
    string map[N];
    for (int i = 0; i < N; i++) cin >>map[i];

    priority_queue<Node, vector<Node>, Compare> q;

    int counts[N][N], results[N][N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            results[i][j] = 0;
            counts[i][j] = -1;
            if (map[i][j] == 'S') {
                q.push({i, j, 0});
            }
        }
    }

    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};


    while (q.size()) {
        auto [x,y,c] = q.top(); q.pop();
        int nc = c+1;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (map[nx][ny] == '1') continue;
            if (counts[nx][ny]>-1 || results[nx][ny]) continue;
            counts[nx][ny] = nc;

            if (map[nx][ny] == 'K') {
                results[nx][ny] = nc;
                q.push({nx, ny, 0});
            } else {
                q.push({nx, ny, nc});
            }
        }
    }

    int result = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == 'K' && results[i][j]) {
                result += results[i][j];
                K--;
            }
        }
    }

    if (K>0) result=-1;

    cout << result;

}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    solve();
    return 0;
}

pjshwa 2달 전 2

아래와 같은 경우에 답을 잘못 출력합니다. (1, 4) 의 K로 이동하여, 거기서 로봇을 복제하여 (1, 1) 로 하나 이동시키는 것이 최적입니다.

5 2
K11K1
00001
11011
1S011
11111

Answer: 10

tjdgnsqn3 2달 전 0

7 2

1111111

1K11K11

1000011

1110111

11S0111

1111111

(시작점, 좌표) pair를 이용해서 처리했지만 틀리는군요..

더 추가로 고려할만한 사항이 있을까요?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node {
    int x,y, c;
    pair<int,int> s;
};

struct Compare {
    bool operator()(const Node &a, const Node &b) {
        return a.c > b.c;
    }
};

int ans[250][250];
void solve(){
    int N, K; cin >> N >>K;
    string arr[N];
    for (int i = 0; i < N; i++) cin >>arr[i];

    priority_queue<Node, vector<Node>, Compare> q;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 'S') {
                q.push({i, j, 0, {i,j}});
            }
        }
    }

    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    memset(ans, -1, sizeof(ans));
    set<pair<pair<int,int>,pair<int,int>>> results;
    while (q.size()) {
        auto [x,y,c, starts] = q.top(); q.pop();
        int nc = c+1;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (arr[nx][ny] == '1') continue;
            if (!results.count({starts, {nx,ny}})) {
                results.insert({starts, {nx,ny}});
                if (arr[nx][ny] == 'K') {
                    if (ans[nx][ny]==-1) ans[nx][ny] = nc;
                    q.push({nx, ny, 0, {nx,ny}});
                    results.insert({{nx,ny},{nx,ny}});
                } else {
                    q.push({nx, ny, nc, starts});
                }
            }
        }
    }

    int result = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 'K' && ans[i][j]>-1) {
                result += ans[i][j];
                K--;
            }
        }
    }

    if (K>0) result=-1;

    cout << result;

}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    solve();
    return 0;
}

pjshwa 2달 전 2

반례를 하나 더 드립니다. M+1 개의 정점이 있는 완전 그래프에서, 간선의 비용 합을 최소화하도록 M 개의 간선을 고르는 문제로 접근해 보시면 좋을 것 같습니다.

5 3
11111
1K00K
11K1S
11111
11111

Answer: 6

tjdgnsqn3 2달 전 1

풀었습니다. 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

로봇은 멈추지 않나요?

tjdgnsqn3 2달 전 0

tjdgnsqn3 2달 전 1

pjshwa 2달 전 2

tjdgnsqn3 2달 전 0

pjshwa 2달 전 2

tjdgnsqn3 2달 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말