글 읽기 - 3일 연속 매달려 봤는데 해결하지 못하고 있습니다.

dudgh9661 3년 전 0

실패되는 테스트 케이스를 찾았으나 해당 테스트 케이스에서 왜 실패하는지 도대체 모르겠습니다ㅑ...

제 코드의 논리적 오류가 어떤 부분인지 알려주시면 정말 감사드리겠습니다. 고통스럽습니다...

다음은 실패하는 테스크 케이스입니다.

36 40
*...................................
.*..*....************************...
..*..*...*C.....................*...
......*..********************...*...
.............................*.*....
..************************..*...*...
.*.......................*.*...*...*
*..********************..*..**.*....
......................*.....*..*....
............*..........*.*.*....*...
*******************.*..**.*.....*...
..................*...*........*....
.**************...*...*.*******...*.
..............*...*...*.............
.*............*...*...*...*.........
.*.************...*...*..*.*........
**............*...*...*.*...*.......
..*...........*...*...**.....*......
...*..........*...*...*.*.....*.....
....*.........*...*...*..*..........
.....*........*...*...*...*.........
......*.......*.*.*...*....*.......*
.......*......*...*...*.....*.....*.
*************.*...*...*......*...*..
*.............*...*...*.......*.*...
*..*..*...*....*..**..*........*....
*..*.*.*.*.**.*...*...*.............
*..**...*....*....*...*.............
*..*..............*...*.............
*..*.**************...*.............
*..*..............*...*.............
**C*.............*....*.............
..*.............*.....*.............
...............*......*.............
......................*.............
......................*.............
***.***.*.*.*.***.***..*..*.*...***.
*...*.*.*.*.*.**..***..*..*.*...**..
*...*.*..*.*...**.*.*..*..*.*...*...
***.***..*.*..***.*..*.****.***.***.

#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>

using namespace std;

int H, W;
int ans = 0;

pair<int,int> start{-1,-1};
pair<int,int> target{-1,-1};
int arr[101][101] = { 0 };
int visited[101][101] = { 0 };

int UD[4] = {1,-1,0,0};
int LR[4] = {0,0,-1,1};
/*
 * output : the number of min mirror
 */

void Print() {
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            if( visited[i][j] == 1e7 ) cout << 0 << " ";
            else cout << visited[i][j] << " ";
        }
        cout << endl;
    }
}
typedef struct pos{
    int r, c, arrow;
}POS;

bool inRange(int r, int c) {
    if (r >= H || r < 0 || c >= W || c < 0 || arr[r][c] == -100 ) return false;
    else return true;
}

void BFS() {
    queue<POS> que; //r,c, arrow
    for(int i = 0; i < 4; i++) {
        int nr = start.first + UD[i];
        int nc = start.second + LR[i];
        if (inRange(nr, nc)) {
            que.push(POS{nr, nc, i});
            visited[nr][nc] = 1;
        }
    }
    visited[start.first][start.second] = 1;

    while( !que.empty() ) {
        int r = que.front().r;
        int c = que.front().c;
        int arrow = que.front().arrow; //pre arrow;
        que.pop();

        for(int i = 0; i < 4; i++) {
            int nr = r + UD[i];
            int nc = c + LR[i];
            if( inRange(nr,nc) ) {
                if (arrow == i) {
                    if (visited[nr][nc] >= visited[r][c]) {
                        visited[nr][nc] = visited[r][c];
                        que.push({nr, nc, i});
                    }
                } else if (arrow != i) {
                    if (visited[nr][nc] >= visited[r][c] + 1) {
                        visited[nr][nc] = visited[r][c] + 1;
                        que.push({nr, nc, i});
                    }
                }
            }
        }
    }
}

void init() {
    cin >> W >> H;

    char ch;
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            visited[i][j] = 1e7;
            cin >> ch;
            if( ch == '.') {
                arr[i][j] = 0;
            } else if (ch == 'C') {
                arr[i][j] = 100;
                if( start.first == -1) {
                    start.first = i;
                    start.second = j;
                } else {
                    target.first = i;
                    target.second = j;
                }

            } else if (ch == '*') {
                arr[i][j] = -100;
            }
        }
    }
}
int main() {
    init();
    BFS();
//    printf("%d %d and %d %d\n", start.first, start.second, target.first, target.second);
    Print();
    cout << visited[target.first][target.second] - 1<< endl;
    return 0;
}

alexroh 3년 전 0

한 달 전 질문인 걸 보니 이미 해결하셨을 것 같지만 그래도 써볼게요.

큐에 {nr, nc, i}라는 노드 X가 들어가 있다고 합시다. 이 노드 X는 arrow = i에 맞게 동작할 예정입니다.

그런데 문제는 노드 X가 큐에 들어가고 난 뒤 visited 배열의 내용이 바뀔 수 있다는 것입니다.

노드 X가 큐에 들어가고 난 다음, visited 배열이 다른 방향에서 온 노드에 의해 다른 값으로 업데이트되면 문제가 발생합니다.

이미 상황은 바뀌었으나, 노드 X는 큐에서 자신의 차례가 오면 자신이 기억하는 arrow = i에 맞게 작동할 것이기 때문입니다.

이 부분을 고치면 올바르게 작동하는 코드입니다.

구조체 POS에 visited[nr][nc]을 기억하는 변수 val을 만들고 큐에 que.push({nr, nc, i, val})로 삽입한 뒤,

나중에 큐에서 꺼낼 때 visited[r][c] != cnt라면 continue해서 버리는 방법이 있을 수 있겠네요.

wndyd9557 2년 전 0

좋은 반례 감사합니다.

덕분에 풀었어요 헤헤

wndyd9557 2년 전 0

윗 분의 의견도 좋은 방법이네요

다른 방법으로는

한 정점에서 위, 왼쪽, 아래, 오른쪽으로 이동하며 벽만나기 전까지 모든 정점을 q에 push하면

visited 배열이 업데이트가 되지 않아서 문제가 발생하지 않습니다.

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

문제

문제

출처

ICPC

3일 연속 매달려 봤는데 해결하지 못하고 있습니다.

dudgh9661 3년 전 0

alexroh 3년 전 0

wndyd9557 2년 전 0

wndyd9557 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말