글 읽기 - 고수분들의 도움이 필요합니다~!

leehj8687 4년 전 0

안녕하세요,

일반적인 BFS 탐색문제 + gram 획득시 벽 무시를 고려하여 간단히 풀 수 있다고 생각했는데, 제출결과는 틀렸다고 나옵니다.

계속 고민해봐도 코드에서 어떤 부분이 오류를 발생시키는 지 모르겠네요.

시간내서 도움주시면 정말 감사드리겠습니다.^^

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;
/* https://www.acmicpc.net/problem/17836 */
int n, m, t;
bool gram = false; // gram 획득 여부
// 네 방향 탐색
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
// x좌표, y좌표, gram 획득 여부 (0 = 미획득, 1 = 획득)
int dist[100][100][2];

void bfs(int x, int y, vector<vector<int>>& a){
    queue<pair<int,int>> q;
    // 거리값 -1 초기화
    memset(dist, -1, sizeof(dist));
    q.push(make_pair(x,y));
    
    dist[x][y][0] = 0; // gram이 없고 x,y 에서 시작.

    while(!q.empty()){
        int curX, curY;
        tie(curX, curY) = q.front(); q.pop();

        // gram이 있거나 없을 때의 현재 좌표에서, 주어진 시간 t보다 커지면 시간 내에 해결 불가.
        if(dist[curX][curY][1] > t || dist[curX][curY][0] > t){
            cout << "Fail";
            //continue;
            return;
        }

        // 네 방향 탐색 시작
        for(int dir = 0; dir < 4; dir++){
            int nx = curX + dx[dir];
            int ny = curY + dy[dir];

            // 배열 범위 벗어남
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

            // gram 획득
            if(a[nx][ny] == 2){
                gram = true;
            }

            // gram 획득 시 dist[x][y][1]로 진행. 방문여부 확인 (-1로 초기화했으므로 -1이 아니면 방문한 적이 있음)
            if(gram == true && dist[nx][ny][1] == -1){
                // gram을 최초로 획득했을 경우 dist[curX][curY][1] == -1이다.
                if(dist[curX][curY][1] == -1){
                    // 최초 획득 시 gram이 없는 경우까지의 최소 거리에 1을 더한다.
                    dist[nx][ny][1] = dist[curX][curY][0] + 1;
                }else{
                    // 최초 획득이 아닌 경우
                    dist[nx][ny][1] = dist[curX][curY][1] + 1;
                }
                // 큐에 삽입.
                q.push(make_pair(nx,ny));
            }
                // gram이 없는 상태이고 다음 노드를 방문하지 않았으며 벽이 아닌 경우
            else if(gram == false && dist[nx][ny][0] == -1 && a[nx][ny] != 1){
                // 다음 노드의 거리를 현재 노드까지의 거리에 1을 증가시켜준다.
                dist[nx][ny][0] = dist[curX][curY][0] + 1;
                // 그리고 큐에 삽입.
                q.push(make_pair(nx,ny));
            }
        }
    }

    // 결과 확인.
    // 1. gram 있는 경우와 없는 경우 둘 다 -1이면 방문이 안됐음 (벽으로 막힌 경우)
    if(dist[n-1][m-1][0] == -1 && dist[n-1][m-1][1] == -1){
        cout << "Fail";
    }
        // 2. gram 없는 경우만 -1이면, gram을 가지고 방문을 했으므로 dist[x][y][1]이 최소시간.
    else if(dist[n-1][m-1][0] == -1){
        cout << dist[n-1][m-1][1] << '\n';
    }
        // 3. gram 있는 경우만 -1이면, gram이 없는 상태로 방문을 했으므로 dist[x][y][0]이 최소시간.
    else if(dist[n-1][m-1][1] == -1){
        cout << dist[n-1][m-1][0] << '\n';
    }
        // 4. 둘 다 -1은 아닌데, gram 없는 경우의 값이 더 크다면, gram이 있는 경우가 최소시간.
    else if(dist[n-1][m-1][0] > dist[n-1][m-1][1]){
        cout << dist[n-1][m-1][1] << '\n';
    }
        // 5. 둘 다 -1은 아닌데, gram 있는 경우의 값이 더 크다면, gram이 없는 경우가 최소시간.
    else if(dist[n-1][m-1][0] <= dist[n-1][m-1][1]){
        cout << dist[n-1][m-1][0] << '\n';
    }
}


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

    cin >> n >> m >> t;
    vector<vector<int>> a(n, vector<int>(m));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }

    bfs(0,0, a);

    return 0;
}

lovinix 4년 전 2

전체 코드를 읽어본건 아니지만 일단 아래와 같은 경우에서 틀릴것같습니다.

Input

2 2 1

0 2

0 0

leehj8687 4년 전 0

@lovinix

답변 감사합니다.

값이 작을때를 생각하지 못했네요.

말씀해주신 부분은 31번째 라인 주석처리 및 32번째 라인 추가하여 해결했습니다.

다만 아직도 계속 틀렸다고 하네요..ㅠ

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

문제

문제

출처

ICPC

고수분들의 도움이 필요합니다~!

leehj8687 4년 전 0

lovinix 4년 전 2

leehj8687 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말