글 읽기 - 이제 희망이 안 보여요... 모든 반례는 통과했는데, 바로 틀렸습니다 뜹니다..

curve4403 3년 전 0

이쯤 되니 제 길이 아닌가 싶은 생각까지 드는 중입니다.. 잠깐만 시간내여 제 코드에 대한 리뷰를 남겨주시면 정말 좋을 것 같습니다... .. 전체적인 알고리즘 간단하게 설명드리겠습니다..

1. map (input 데이터) 입력 시 바다와 인접한 외곽 영역 구분을 위해, map의 가로, 세로가 1 ~ N이 아닌, 0, N + 1에 -1을 동시에 넣어줍니다. 그래서 0과 인접하면 바다와 인접한 영토, -1과 인접하면 바다와 인접하지 않은 외곽 영토로 구분했습니다.

2. solution 함수를 호출하자 마자 map의 처음부터 끝까지 순차적으로 탐색해, 1 값인 경우 육지로(새 섬이 될 수 있다고) 판단해, numbering 함수를 호출해 해당 위치를 시작으로 인접한 모든 섬 영토를 파악해 번호를 붙입니다. 이 때 islandCnt은 현재 섬에 넘버링 한 수를 의미하며, islandCnt - 1은 현재까지 순차적으로 탐색해 알아낸 섬의 수를 의미합니다.

3. 해당 섬에 번호를 붙이자 마자, findExpandable 함수를 호출해, islandCnt 값이 매겨진(방금 발견한) 섬에 대해 바다와 인접한 외곽 영토 좌표 값을 찾습니다.

4. expanding 함수를 호출해 islandCnt 값이 매겨진(방금 발견한) 섬의 외곽 영역을 시작으로 다른 섬을 발견할 때까지 현재 섬 외곽 영역을 Q에 모두 enqueue 후, BFS를 이용해 동시에 다리를 건설하기 시작합니다. 이 때 새로 건설한 다리 또한 Q에 모두 enqueue하여 다음 단계 다리를 계속 지어나가며, 다리 건설 위치 및 거리 정보는 expandingMap 배열에 기록하며 중복 섬 일부 영역 탐색에 대한 예외 처리를 위해, expanding 함수에서 다리를 짓다가 새 섬의 '일부 영토'를 발견하면, 그 일부 영토의 중복 발견을 방지하기 위해 해당 영토의 좌표 값을 found에 기록합니다.

도와주세요..........제발.......

/*
 22146 다리 만들기

 대통령은 하나의 섬과 다른 섬을 가장 짧에 이을 다리 하나를 만들어야 한다.

 input
 지도의 크기 N (N <= 100)
 map 정보 (0 = 바다, 1 = 육지)

 output
 가장 짧은 다리의 길이
 */

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

using namespace std;

struct point {
public:
    int r, c;
    point();
    point(int r, int c) : r(r), c(c) {};
};

int N;
int map[102][102];

//상, 하, 좌, 우 이동
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};

int islandCnt = 2;
int minimum = 99999;

void expanding(vector<point> expandable, int islandNumber) {
    int expandingMap[101][101];
    int found[101][101];
    for(int r = 1; r <= N; r++) for(int c = 1; c <= N; c++) expandingMap[r][c] = 0, found[r][c] = 0;

    queue<point> Q;
    for(int i = 0; i < expandable.size(); i++) Q.push(expandable[i]);

    //map 상에서 0 값이면서, islandNumber(현재 다리 건설 진행 중인 출발 섬 영역)가 아닌 current의 next 탐색
    while(!Q.empty()) {
        point current = Q.front();
        Q.pop();

        for(int d = 0; d < 4; d++) {
            point next(current.r + dr[d], current.c + dc[d]);

            //islandNumber(현재 다리 건설 진행 중인 출발 섬 영역) 제외
            if(map[next.r][next.c] == islandNumber) continue;

            //0 아닌 값을 발견한 경우 = 다른 섬을 발견한 경우
            if(map[next.r][next.c] != 0 && next.r != 0 && next.c != 0 && next.r != N + 1 && next.c != N + 1 && found[next.r][next.c] == 0) {
                if(minimum > expandingMap[current.r][current.c]) minimum = expandingMap[current.r][current.c];
                found[next.r][next.c] = 1;
                continue;
            }

            //이미 다리를 지은 영역인 경우 제외
            if(expandingMap[next.r][next.c] != 0) continue;

            //0 값인 경우 = 다리를 지을 수 있는 경우 = Q에 삽입해야 하는 경우
            if(map[next.r][next.c] == 0) {
                Q.push(next);
                expandingMap[next.r][next.c] = expandingMap[current.r][current.c] + 1;
            }
        }
    }
}

//해당 번호 섬의 외곽 영역 모두 탐색
vector<point> findExpandable(int islandNumber) {
    vector<point> expandable;

    for(int r = 1; r <= N; r++) {
        for(int c = 1; c <= N; c++) {
            //바다인 경우
            if(map[r][c] == 0) continue;

            //같은 섬 영역이 아닌 경우
            if(map[r][c] != islandNumber) continue;

            //같은 섬 영역인 경우: 인접 영역이 외곽인지 확인
            for(int d = 0; d < 4; d++) {
                if(map[r + dr[d]][c + dc[d]] == 0) {
                    //외곽 영역인 경우
                    point P(r, c);
                    expandable.push_back(P);
                    break;
                }
            }
        }
    }

    return expandable;
}

void numbering(int r, int c) {
    int visited[101][101];
    queue<point> Q;
    point start(r, c);
    Q.push(start);
    map[start.r][start.c] = islandCnt;
    visited[r][c] = true;

    while(!Q.empty()) {
        point current = Q.front();
        Q.pop();

        //인접 영토(섬 전체) 넘버링
        for(int d = 0; d < 4; d++) {
            point next(current.r + dr[d], current.c + dc[d]);

            //유효 범위 여부 확인
            if(next.r < 1 || next.c < 1 || next.r > N || next.c > N) continue;

            //방문 여부 확인
            if(visited[next.r][next.c]) continue;

            //육지 여부 확인
            if(map[next.r][next.c] == 0) continue;

            map[next.r][next.c] = islandCnt;
            Q.push(next);
            visited[next.r][next.c] = true;
        }
    }
}

void solution() {
    int minimumResult = 99999;

    for(int r = 0; r <= N + 1; r++) {
        for(int c = 0; c <= N + 1; c++) {
            if(map[r][c] == 1) {
                //섬 고유 번호 부여
                numbering(r, c);

                //섬 외곽 영역 탐색
                vector<point> res = findExpandable(islandCnt);

                //섬 외곽 영역을 시작으로 다른 섬을 발견할 때까지 확장
                expanding(res, islandCnt);

                if(minimumResult > minimum) minimumResult = minimum;
                minimum = 99999;

                islandCnt++;
            }
        }
    }

    cout << minimumResult << endl;
}

int main() {
    cin >> N;

    for(int r = 0; r <= N + 1; r++) for(int c = 0; c <= N + 1; c++) {
        if(r == 0 || c == 0 || r == N + 1 || c == N + 1) map[r][c] = -1;
        else cin >> map[r][c];
    }

    solution();

    return 0;
}

kja9294 3년 전 1

numbering 함수 내 visited 배열을 0으로 초기화 해주세요. 지역변수는 초기 값이 0이 아닙니다!!

curve4403 3년 전 0

헐 세상에....... 아니 제가 왜 이걸 못 봤던 걸까요 ㅠㅠㅠㅠㅠㅠㅠㅠㅠ

덕분에 맞았습니다!!! 정말 감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

이제 희망이 안 보여요... 모든 반례는 통과했는데, 바로 틀렸습니다 뜹니다..

curve4403 3년 전 0

kja9294 3년 전 1

curve4403 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말