글 읽기 - 어떤 부분이 틀렸는지 알고 싶습니다!

rain_maker 5년 전 0

게시판에 반례를 다 돌려보았으나 틀렸습니다가 뜹니다.

제가 어떤 실수를 하고 있는지 알고싶어 글을 남깁니다.

많은 조언을 주시면 감사하겠습니다.

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <queue>
using namespace std;

char graph[52][52];
vector<pair<int, int>> B, E;
unordered_map<string, int> visit;

int BFS() {

    string start, end; // B 묶음의 시작 좌표와 E 묶음의 좌표 저장

    for (int i = 0; i < 3; i++) {
        start += to_string(B[i].first);
        start += to_string(B[i].second);
        end += to_string(E[i].first);
        end += to_string(E[i].second);
    }

    visit.insert(make_pair(end, 987654321)); // B 묶음이 도달한다면 최소값 갱신 예정
    visit.insert(make_pair(start, 1)); // B 묶음 시작 좌표 - 방문함

    queue<vector<pair<int, int>>> q;
    q.push(B);

    while (!q.empty()) {

        auto here = q.front(); q.pop(); // 변화 좌표를 가진 B 묶음 꺼냄 - 첫 라운드엔 시작 좌표

        string value;
        for (int i = 0; i < 3; i++) {
            value += to_string(here[i].first);
            value += to_string(here[i].second);
        }

        vector<pair<int, int>> up, down, right, left, turn;
        up = down = right = left = turn = here; // 좌표를 변화시킬 B 묶음 목록

        up[0].first--; up[1].first--; up[2].first--;
        down[0].first++; down[1].first++; down[2].first++;
        right[0].second++; right[1].second++; right[2].second++;
        left[0].second--; left[1].second--; left[2].second--;

        bool rv = false;
        if (turn[0].first == turn[1].first &&
            turn[1].first == turn[2].first) { // 현재 B 묶음이 가로일 때
                turn[0] = make_pair(turn[1].first - 1, turn[1].second);
                turn[2] = make_pair(turn[1].first + 1, turn[1].second);
            }
            else { // 현재 B 묶음이 세로일 때
                turn[0] = make_pair(turn[1].first, turn[1].second - 1);
                turn[2] = make_pair(turn[1].first, turn[1].second + 1);
                rv = true; // 현재 세로임을 증명
            }

        vector<vector<pair<int, int>>> list; // 차례대로 리스트에 넣음
        list.push_back(up); list.push_back(down); list.push_back(right); 
        list.push_back(left); list.push_back(turn);

        for (int i = 0; i < 5; i++) {

            bool tree = false;
            string overlab;

            if (i == 4 && !tree) { // 4번째에 turn 을 했을시의 좌표 정보가 있다.
                if (rv) {
                    for (int i = here[0].first; i <= here[2].first; i++) {
                        if (graph[i][here[0].second - 1] == '1' ||
                            graph[i][here[0].second + 1] == '1') {
                                tree = true;
                                break;
                            }
                    }
                }
                else {
                    for (int i = here[0].second; i <= here[2].second; i++) {
                        if (graph[here[0].first - 1][i] == '1' ||
                            graph[here[0].first + 1][i] == '1') {
                                tree = true;
                                break;
                            }
                    }
                }
            }

            for (int j = 0; j < 3 && !tree; j++) { // 그외의 변화된 좌표 정보
                if (graph[list[i][j].first][list[i][j].second] == '1') { // 이동하려는 곳에 1이 있을 경우 멈춤
                    tree = true;
                    break;
                }
                overlab += to_string(list[i][j].first);
                overlab += to_string(list[i][j].second);
            }

            if (!tree && visit[overlab] == 0) { // 1이 없으면서 방문하지 않은 좌표 (B묶음이 해당 형태를 가지는 것이 처음인 경우)
                visit[overlab] = visit[value] + 1;
                q.push(list[i]);
            }
            else if (!tree && overlab == end) { // 1이 없으면서 해당 형태의 좌표가 E 묶음이 있는 곳인 경우
                if (visit[end] > visit[value] + 1) { // 최소 값 갱신
                    visit[end] = visit[value] + 1;
                }
            }
        }
    }
    return visit[end];
}

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

    int n; cin >> n;

    // 둘레
    for (int i = 0; i < n + 2; i++) {
        graph[0][i] = '1';
        graph[n + 1][i] = '1';
    }
    for (int i = 1; i < n + 1; i++) {
        graph[i][0] = '1';
        graph[i][n + 1] = '1';
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> graph[i][j];
            if (graph[i][j] == 'B') { 
                B.push_back(make_pair(i, j)); // B의 위치
                graph[i][j] = '0'; // 그래프 상에선 지움
            }
            else if (graph[i][j] == 'E') { 
                E.push_back(make_pair(i, j)); // E의 위치
                graph[i][j] = '0'; // 그래프 상에선 지움
            }
        }
    
    int result = BFS() - 1; // 시작 상태일 때 1이었기 때문에 -1함.

    if (result == 987654320) { // B가 E에 도달하지 못한 경우
        cout << 0;
    }
    else { 
        cout << result; // 도달한 경우
    }

    return 0;
}

evenharder 5년 전 1

여기에 반례가 나와 있습니다.

https://www.acmicpc.net/board/...

Input:
4
000B
100B
100B
EEE0

Output:
0

rain_maker 5년 전 0

해당 반례를 넣었을 때 출력이 5가 나오는데 정상 아닌가요??

YunGoon 5년 전 4

B, E의 좌표를 저장하고 이를 스트링으로 변환하여 연결하신 후 맵의 키값으로 쓰셨는데,

아래 데이터와 같이 (1, 11) (1, 12) (1, 13) 일때와 (11, 1) (11, 2) (11, 3) 일때 만들어지는 키가 동일합니다.

input
13
0000000000BBB
0000000000000
0000000000000
0000000000000
0000000000000
0000000000000
0000000000000
0000000000000
0000000000000
0000000000000
EEE0000000000
0000000000000
0000000000000

answer
20

output
0

rain_maker 5년 전 0

아아 감사합니다 덕분에 풀었습니다! 그저 빛

ploffer11 5년 전 4

랜덤 테케 넣다가 반례가 안나와서 답을 못드렸는데, 엉뚱한 곳에 문제가 있었군요.

후에 다른 분들이 이 문제를 풀 때 도움 되라고

만든 케이스들을 남겨두고 가겠습니다.

8
BBB00000
00000000
00000000
10111111
10100000
00000000
00000000
00000EEE
answer : 14

4
BBB1
1111
1111
1EEE
answer : 0


4
BBB0
000E
000E
000E
answer : 5

4
B000
B000
B000
0EEE
answer : 5

4
EEE0
0000
0000
0BBB
answer : 4

5
0BEEE
0B000
0B011
11111
11111
answer : 4

4
BBB0
0000
1000
EEE0
answer : 5

7
BBB0000
0111000
0111000
0001101
1111000
EEE0000
1111000
answer : 15

6
BBB000
001000
0010E0
0000E0
0000E0
000000
answer : 7

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

문제

문제

출처

ICPC

어떤 부분이 틀렸는지 알고 싶습니다!

rain_maker 5년 전 0

evenharder 5년 전 1

rain_maker 5년 전 0

YunGoon 5년 전 4

rain_maker 5년 전 0

ploffer11 5년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말