글 읽기 - 왜 틀렸는지 모르겠어요!!! 다양한 반례도 넣어봤는데

tingko 5년 전 0

큐에 물을 먼저 넣고 고슴도치를 나중에 넣는 식으로 해서 물이 먼저 차오르고 고슴도치가 나중에 이동하는 로직입니다.

추가 테스트 케이스도 한 20여개 찾아서 넣어 봤음에도 모든 테스트 케이스가 다 맞다고 하는데 왜 틀렸다고 나오는지 모르겠네요..

// BOJ 3055 탈출
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

struct pt {
    char type; // S = 고슴도치 * = 물
    int x, y, t;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // . 비어있는곳
    // * 물차있는곳
    // X 돌
    // D 비버굴 (목적지)
    // S 고슴도치

    int N, M;
    cin >> N >> M;
    vector<vector<char> > arr(N + 2, vector<char>(M + 2, 'X'));
    vector<vector<bool> > visited(N + 2, vector<bool>(M + 2, false));

    pt go, wat; // 고슴도치, 물
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 'S') {
                go = {'S', i, j, 0}; // 고슴도치
                visited[i][j] = true;
                arr[i][j] = '.'; // 고슴도치 자리를 빈공간으로
            } else if (arr[i][j] == '*')
                wat = {'*', i, j, 0}; // 물
        }
    }
    queue<pt> Q;
    Q.push(wat);
    Q.push(go);

    while (!Q.empty()) {
        pt cur = Q.front();
        Q.pop();
        int x = cur.x;
        int y = cur.y;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 물일 경우
            if (cur.type == '*' && arr[nx][ny] == '.') {
                arr[nx][ny] = '*';
                Q.push({'*', nx, ny, cur.t + 1});
            }
            // 고슴도치일 경우
            else if (cur.type == 'S' && arr[nx][ny] == '.'
                     && !visited[nx][ny]) {
                visited[nx][ny] = true;
                Q.push({'S', nx, ny, cur.t + 1});
            }
            // 고슴도치면서 비버굴
            else if (cur.type == 'S' && arr[nx][ny] == 'D') {
                cout << cur.t + 1;
                exit(0);
            }
        }

        // 현재 큐가 물인데 다음 큐가 고슴도치가 아니면서
        // 시간대는 다음 단계라면
        // == 고슴도치가 큐에서 아예 사라졌을 때
        // == 더 이상 고슴도치가 이동할 곳이 없을 때
        if (cur.type == '*' && Q.front().type != 'S'
            && (cur.t < Q.front().t)) {
            cout << "KAKTUS";
            exit(0);
        }
    }
    cout << "KAKTUS";

    return 0;
}

seico75 5년 전 2

초기에 물은 한곳에만 있는 것은 아닌 것 같습니다.

즉, * 가 여러개 있을 수 있지 않을까요?

tingko 5년 전 0

seico75님 감사합니다!

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠어요!!! 다양한 반례도 넣어봤는데

tingko 5년 전 0

seico75 5년 전 2

tingko 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말