글 읽기 - (상세 설명 有)(C++) 60% 언저리에서 계속 틀립니다.

tmdwp54977 1년 전 0

각 함수의 역할은

bfsRemap() : 처음에 모두 1로 들어왔던 섬 정보에 대해, 서로 다른 섬에 속하는 요소들은 서로 다른 숫자로 바꿔주는 함수

bfsBridge() : bridge_visit[][] == 0이면서 주위 네 방향에 대해 섬이 존재한다면, 해당 지점에서 BFS를 돌려 가장 짧은 다리 찾기

각 변수들의 역할은

map : 땅 정보 저장

bridge : 더 짧은 다리 길이를 저장하는 변수

length[] : 가장 짧은 다리를 BFS로 찾을 때 다리 길이를 저장하는 queue

bridge_visit[][] : bfsRemap() 실행 후, map 값이 0인 지점들에 대한 방문 여부 체크

입니다.

visit[][]을 bfsBridge()가 실행될 때마다 초기화 시켜줬고, 직접 값을 찍어보면서 주위 네 방향 중 한 방향이라도 섬이 존재하는 경우에만 bfsBridge()가 실행된다는 것도 확인했습니다. queue가 다 빌 때까지 계속 수행하여 더 짧은 값을 찾지 못하고 끝나는 경우도 없습니다. 결국 bfsBridge() 내 46 ~ 60번째 줄 내에 오류가 있다고 생각했는데, 제 논리에 대한 반례가 언제인지 궁금합니다. 혹은 다른 부분에서 실수하고 있는 것이 있다면 알려주세요.

Line 46 : 현재 좌표 값에 대해 +dx, +dy를 했을 때 맵을 벗어나는 값이 있다면 해당 경우는 더이상 탐색할 필요가 없으므로 continue

Line 49 : 현재 좌표 값에 대해 +dx, +dy를 했을 때 해당 지점이 0이 아닌 값, 즉 육지라면

Line 50 : 그 값이 bfsBridge()의 세번째 인자인 island와 다르다면, 즉 다른 섬을 만났고 해당 지점까지의 다리 길이가 더 짧다면 bridge를 갱신
해당 지점이 island와 같든 다르든, 해당 방향으로 +dx, +dy를 해봤자 Line 55에 의해 queue에 들어가지 않으므로 반드시 continue

Line 55 : visit은 map[][] == 0일때, 즉 바다에 대해서만 수행함

#include <stdio.h>
#include <string.h>

int n, land_num = 1, front, rear, bridge = 10001, map[105][105], queue_x[10201], queue_y[10201], length[10201];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
bool visit[105][105], bridge_visit[105][105];

void bfsRemap(int y, int x) {

    int i;

    visit[y][x] = 1, map[y][x] = land_num;
    front = -1, rear = 0;
    queue_y[0] = y, queue_x[0] = x;

    while(front < rear) {
        
        front++;
        for(i = 0; i < 4;i++) {
            if(queue_x[front] + dx[i] < 1 || queue_x[front] + dx[i] > n || queue_y[front] + dy[i] < 1 || queue_y[front] + dy[i] > n)
                continue;
            if(visit[queue_y[front] + dy[i]][queue_x[front] + dx[i]] == 0 && map[queue_y[front] + dy[i]][queue_x[front] + dx[i]] != 0) {
                queue_y[++rear] = queue_y[front] + dy[i];
                queue_x[rear] = queue_x[front] + dx[i];
                visit[queue_y[front] + dy[i]][queue_x[front] + dx[i]] = 1;
                map[queue_y[front] + dy[i]][queue_x[front] + dx[i]] = land_num;
            }
        }
    }
}

void bfsBridge(int y, int x, int island) {

    int i;

    memset(visit, 0, sizeof(visit));
    visit[y][x] = length[0] = 1;
    front = -1, rear = 0;
    queue_y[0] = y, queue_x[0] = x;

    while(front < rear) {
        
        front++;
        for(i = 0; i < 4;i++) {

            if(queue_x[front] + dx[i] < 1 || queue_x[front] + dx[i] > n || queue_y[front] + dy[i] < 1 || queue_y[front] + dy[i] > n)
                continue;

            if(map[queue_y[front] + dy[i]][queue_x[front] + dx[i]] != 0) {
                if(map[queue_y[front] + dy[i]][queue_x[front] + dx[i]] != island && length[front] < bridge)
                    bridge = length[front];
                continue;
            }

            if(visit[queue_y[front] + dy[i]][queue_x[front] + dx[i]] == 0 && map[queue_y[front] + dy[i]][queue_x[front] + dx[i]] == 0) {
                queue_y[++rear] = queue_y[front] + dy[i];
                queue_x[rear] = queue_x[front] + dx[i];
                length[rear] = length[front] + 1;
                visit[queue_y[front] + dy[i]][queue_x[front] + dx[i]] = 1;
            }
        }
    }
}

int main() {

    int i, j, k;

    scanf("%d", &n);

    for(i = 1;i <= n;i++) {
        for(j = 1;j <= n;j++)
            scanf("%d", &map[i][j]);
    }

    for(i = 1;i <= n;i++) {
        for(j = 1;j <= n;j++) {
            if(visit[i][j] == 0 && map[i][j] != 0) {
                bfsRemap(i, j);
                land_num++;
            }
        }
    }

    for(i = 1;i <= n;i++) {
        for(j = 1;j <= n;j++) {
            if(map[i][j] == 0 && bridge_visit[i][j] == 0) {
                for(k = 0;k < 4;k++) {
                    if(map[i + dy[k]][j + dx[k]] != 0)
                        bfsBridge(i, j, map[i + dy[k]][j + dx[k]]);
                }
                bridge_visit[i][j] = 1;
            }
        }
    }

    printf("%d", bridge);

    return 0;
}

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