글 읽기 - 모든 TC를 적용하고 통과했지만 1프로 틀렸습니다가 나옵니다...

gkswns3708 3년 전 0

특정 부분 로직이 잘못되었다 - 가장 가능성 큼.. 하지만 제 실력으로는 못 찾겠습니다.

메모리 침범 -> 0,1 +1, +2 이런식으로 코드에 작은 흠이 있을 수 있다. - >찾아봐서 나름 해결했지만 그래도 1프로 틀렸습니다가 나왔습니다.

이제 제 코드의 메인 로직을 설명드리겠습니다.

먼저 BFS탐색으로 모든 섬을 구별해 1,2,3,4,5,6으로 각 섬을 색칠합니다, 그와 동시에 islandpos에 BFS탐색을 시작하는 곳을 저장해 후에 다리를 놓을 때 그 곳을 시작점으로 BFS를 해 다리를 놓습니다

섬 BFS가 끝난 후 다리를 놓는 로직은

현재 내가 고려중인 곳이 섬의 한 부분이다 -> 상하좌우로 갈 수 있다(possiblearr통과) -> 다음 이동할 곳이 0이다(바다) 그럼 일단 다리를 놓습니다 매개 변수로 dir,y,x,현재섬 번호를 넘겨서 현재 0인(바다)인 곳에서 dir방향으로 1자로 갑니다. 이때 길을 놓았때 지도상 밖으로 나가거나 섬을 만났을 경우 break 합니다. 이때 섬이 같은 섬이면 거리를 갱신하지 않고, 다른 섬일 때 + 거리가 2이상일 때만 갱신을 합니다

- 이 때 visit이 맵상의 0인 부분을 체크하지 않는데 이유는 한 공간에 다른 다리가 충분히 올 수 있다고 생각했기 때문.

위 과정이 끝나면 2차원배열 dist에 2차원으로 각 거리의 최소값이 갱신되어 있을 것이고, 이것을 이용해 MST(크루스칼 알고리즘 이용)을 하면 -1 or MST결과값을 출력하게 햇습니다.

게시판 및 문제의 모든 예제가 통과했습니다만 1프로 틀렸습니다가 나옵니다.

불쌍한 중생하나 살려주세요.

#include <bits/stdc++.h>
#define INF  987654321
using namespace std;
int arr[11][11];
int islandcnt = 1;
int N, M;
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
vector<pair<int, int>> islandpos;
bool visit[11][11];
int dist[7][7];

bool possible(int y, int x) {
    if (y >= 0 && y < N && x >= 0 && x < M && visit[y][x] != true && arr[y][x] ==1) return true;
    else return false;
}
bool possiblearr(int y, int x) {
    if (y >= 0 && y < N && x >= 0 && x < M && visit[y][x] != true) return true;
    else return false;
}

void BFS(int y, int x) {
    queue<pair<int, int>> que;
    que.push({ y,x });
    visit[y][x] = true;
    arr[y][x] = islandcnt;

    while (!que.empty()) {
        int nowy = que.front().first;
        int nowx = que.front().second;
        que.pop();

        for (int i = 0; i < 4; i++) {
            int newy = nowy + dy[i];
            int newx = nowx + dx[i];
            if (possible(newy, newx)) {
                que.push({ newy,newx });
                visit[newy][newx] = true;
                arr[newy][newx] = islandcnt;
            }
        }
    }
}

void makeroad(int y, int x, int dir,int cnt) {
    int len = 0;
    int nowy = y;
    int nowx = x;
    while (1) {
        if (arr[nowy][nowx] != 0) {
            break;
        }
        if (possiblearr(nowy, nowx)) {
            nowy = nowy + dy[dir];
            nowx = nowx + dx[dir];
            len++;
        }
        else break;
    }
    //길을 놓았는데 같은 섬이거나 섬을 만나지 못한경우
    if (arr[nowy][nowx] == cnt || arr[nowy][nowx] == 0) {
        return;
    }
    //현재 시작 섬 도착섬 거리 갱신
    if (len >= 2) {
        dist[cnt][arr[nowy][nowx]] = min(dist[cnt][arr[nowy][nowx]], len);
    }
    return;
}

void make_bridge(int y, int x, int cnt) {
    queue<pair<int, int>> que;
    que.push({ y,x });
    visit[y][x] = true;

    while (!que.empty()) {
        int nowy = que.front().first;
        int nowx = que.front().second;
        que.pop();

        for (int i = 0; i < 4; i++) {
            int newy = nowy + dy[i];
            int newx = nowx + dx[i];
            if (possiblearr(newy, newx) ) {
                if (arr[newy][newx] == cnt) {
                    que.push({ newy,newx });
                    visit[newy][newx] = true;
                }
                if (arr[newy][newx] == 0) {
                    makeroad(newy, newx, i,cnt);
                }
            }
            
        }
    }
}
int parent[7];
int Find(int x) { return x == parent[x] ? x : parent[x] = Find(parent[x]); }
void Union(int a, int b) { a < b ? parent[b] = a : parent[a] = b; }

int MST() {
    vector<tuple<int, int, int>> vectu;
    for (int i = 0; i < 7; i++) {
        parent[i] = i;
    }
    for (int i = 1; i < islandcnt; i++) {
        for (int j = 1; j < islandcnt; j++) {
            if (dist[i][j] != INF) {
                vectu.push_back({ dist[i][j],i,j });
            }
        }
    }
    sort(vectu.begin(), vectu.end());
    int sum = 0;
    int can = 0;
    for (int i = 0; i < vectu.size(); i++) {
        int a = get<0>(vectu[i]);
        int b = get<1>(vectu[i]);
        int c = get<2>(vectu[i]);
        b = Find(b), c = Find(c);
        if (b == c) continue;
        Union(b, c);
        sum += a;
        can++;
        //cout << can << " " << islandcnt << "\n";
        if (can == islandcnt - 2) break;
    }
    if (can != islandcnt - 2) return -1;
    else return sum;
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
    
    for (int i = 0; i < N; i++) 
        for (int j = 0; j < M; j++) 
            if (visit[i][j] != true && arr[i][j] == 1) {
                BFS(i, j);
                islandcnt++;
                islandpos.push_back({ i,j });
            }
    //----------------- 모든 섬 구별완료
    //이제 필요한 다리 설치
    fill(&dist[0][0], &dist[6][7], INF);
    for (int i = 0; i < islandpos.size(); i++) {
        int nowy = islandpos[i].first;
        int nowx = islandpos[i].second;
        for (int j = 0; j < 11; j++) {
            for (int k = 0; k < 11; k++) {
                visit[j][k] = false;
            }
        }
        make_bridge(nowy, nowx,i+1);
    }
    

    cout << MST() << "\n";
    return 0;
}

ohsemin4 3년 전 1

예제부터 돌아가지 않는 것 같습니다.

그것과 상관없이 61~63번째줄에서

if (arr[nowy][nowx] == cnt || arr[nowy][nowx] == 0) {

return;

}

이부분에서 인덱스 에러가 나지 않을까요? nowy와 nowx가 -1이거나 침범할수도 있어 보입니다.

gkswns3708 3년 전 0

풀코드는 스포라 못 보여드리고

요런식으로 먼저 계산 후 index계산을 하니까 맞네요

뭔가 의심은 하고 있었는데 어딘지를 콕 찝어주셔서 맞을 수 있었습니다

감사합니다.

 while (1) {
        if (possiblearr(nowy+dy[dir], nowx+dx[dir])) {
            nowy += dy[dir];
            nowx += dx[dir];
            len++;
        }
        else {
            break;
        }
        //현재 밟고 있는 곳이 섬이라면 break;
        if (arr[nowy][nowx] != 0) {
            break;
        }
    }

gkswns3708 3년 전 0

뭔가 당연히 해야하는건데 코드가 길어지니 그냥 대충 맞아라 체념했었는데... 한번 더 감사합니다.

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

문제

문제

출처

ICPC

모든 TC를 적용하고 통과했지만 1프로 틀렸습니다가 나옵니다...

gkswns3708 3년 전 0

ohsemin4 3년 전 1

gkswns3708 3년 전 0

gkswns3708 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말