글 읽기 - 목적지 C에 도착했다는 것을 판별하는 저의 방법이 왜 틀렸는지 궁금합니다.

kangbada0728 5년 전 1

목적지 C에 도착했을때 이를 판별하는 저의 방법이 왜 틀렸는지 궁금합니다.

문제가 되는 부분은 코드에서 ////////여기가 문제//////////// 라고 되어있는 부분의 바로 밑 if문입니다.

저는 임의의 C를 시작지점으로 잡고 bfs를 수행하다가 C를 만난 경우, 이것이 시작지점의 x, y좌표와 다르면 이를 도착지점으로 판별하게 했습니다.

C가 두개밖에 없었기에 문제가 없을 줄 알았는데 틀렸다고 결과가 나오더군요.

그래서 아예 도착지점의 C좌표를 가져와서 딱 이 C좌표와 동일한 경우에만 도착지점으로 판별하게 했더니 통과하더군요.

여러번 반복하면서 시도도 해봤는데 대체 이게 왜 다른지 알수가 없더군요.

뭐가 문제일까요?

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

int W=0, H=0;
int result = 0xfffffff;

class aaa{
public:
    int x;
    int y;
    int d;
    int c;
    
    aaa(int x, int y, int d, int c){
        this->x = x;
        this->y = y;
        this->d = d;
        this->c = c;
    }
};

int xx[4] = {0, 0, 1, -1};
int yy[4] = {1, -1, 0, 0};
// east 0, west 1, south 2, north 3
void bfs(const vector< vector<char> >& matrix, const pair<int, int> s1, const pair<int, int> s2)
{
    queue<aaa> arr;
    arr.push(aaa(s1.first, s1.second, -1, 0));
    vector< vector<int> > check(H, vector<int>(W, 0xfffffff));
    check[s1.first][s1.second] = 0;
    
    while(!arr.empty())
    {
        int x = arr.front().x;
        int y = arr.front().y;
        int d = arr.front().d;
        int c = arr.front().c;
        arr.pop();
        
        //////////////////////////////여기가 문제///////////////////////////////////////////
        if(matrix[x][y]=='C' && (s1.first!=x && s1.second!=y)) // 기존 도착 판별문(통과 못함)
        {//if(matrix[x][y]=='C' && (s2.first==x && s2.second==y)) // 새로운 도착 판별문(통과함)
        /////////////////////////////////////////////////////////////////////////////////
            if(result>c)
                result=c;
            continue;
        }
        
        for(int i=0; i<4; i++)
        {
            int nx = x+xx[i];
            int ny = y+yy[i];
            // east 0, west 1, south 2, north 3
            
            if((d==0 && i==1) || (d==1 && i==0) || (d==2 && i==3) || (d==3 && i==2))
                continue;
            
            if(0<=nx && nx<H && 0<=ny && ny<W && matrix[nx][ny]!='*')
            {
                int cc = c;
                if(d!=i && d!=-1){
                    cc++;
                }
                
                if(check[nx][ny]>=cc)
                {
                    check[nx][ny] = cc;
                    arr.push(aaa(nx, ny, i, cc));
                }
            }
        }
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>W>>H;
    
    vector< vector<char> > matrix(H, vector<char>(W));
    vector< pair<int, int> > s;
    string a;
    for(int i=0; i<H; i++)
    {
        cin>>a;
        for(int j=0; j<W; j++)
        {
            matrix[i][j] = a[j];
            if(matrix[i][j]=='C')
            {
                s.push_back(make_pair(i, j));
            }
        }
    }
    
    bfs(matrix, s[0], s[1]);
    
    cout<<result;
    
    return 0;
}

notorioush2 5년 전 2

if(matrix[x][y]=='C' && (s1.first!=x && s1.second!=y)) 를

if(matrix[x][y]=='C' && (s1.first!=x || s1.second!=y))

로 바꿔야 합니다.

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

문제

문제

출처

ICPC

목적지 C에 도착했다는 것을 판별하는 저의 방법이 왜 틀렸는지 궁금합니다.

kangbada0728 5년 전 1

notorioush2 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말