글 읽기 - 2206번 반례좀 찾아주세요ㅠㅠ

kysu5095 4년 전 0

질문게시판 보면서 반례들을 넣어봤는데 답은 잘 나오는데

계속 틀렸다고 나오네요. 어느부분이 틀린건가요..?ㅜㅜ

//  벽 부수고 이동하기  //
////////////////////////

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int n, m;
int path = 1;
bool visited[1000][1000] = { {false, }};
string* arr;

class Point{    // 좌표 이동용 클래스
    public:
        int x, y;
};
Point p[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

class Wall{     // 해당 벽에대한 정보
    public:
        int x, y, check;
};
queue<Wall> q;

int bfs(){
    q.push({0, 0, 0});

    while(!q.empty()){
        int size = q.size();

        for(int j = 0; j < size; j++){
            int x = q.front().x;
            int y = q.front().y;
            int check = q.front().check;
            if(x == m - 1 && y == n - 1) return path;

            for(int i = 0; i < 4; i++){
                int nextX = x + p[i].x;
                int nextY = y + p[i].y;

                if(nextX >= 0 && nextX < m && nextY >= 0 && nextY < n){ // 해당 좌표가 범위 안에 있고
                    if(arr[nextY][nextX] == '0') { // 그 좌표가 뚤려있을 때
                        if(check == 0){ // 아직 벽을 부순적이 없음
                            q.push({nextX, nextY, 0});
                        }
                        else{ // 벽을 부순적이 있다면
                            q.push({nextX, nextY, 1});
                        }
                    }
                    else if(arr[nextY][nextX] == '1' && check == 0){ // 그 좌표가 벽이지만 벽을 부순적이 없다면
                        q.push({nextX, nextY, 1});
                    }
                }
            }
            q.pop();
            if(q.size() == 0 && (x != m - 1 || y != n - 1)) return -1;
        }
        path++;
    }
}

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

    cin >> n >> m;
    arr = new string[n];
    for(int i = 0; i < n; i++){
        cin >> arr[i]; // 판 만들기
    }

    if(n == 1 && m == 1) cout << 1 << '\n';
    else cout << bfs() << '\n';

    delete[] arr;
    return 0;
}

3587jjh 4년 전 0

57째줄: 큐를 pop하는 시점이 잘못됐습니다

12째줄: bfs가 visited배열을 전혀 활용하고 있지 않습니다

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

문제

문제

출처

ICPC

2206번 반례좀 찾아주세요ㅠㅠ

kysu5095 4년 전 0

3587jjh 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말