글 읽기 - [C언어] 틀린 부분이 눈에 보이질 않네요. 고수님들의 도움이 필요합니다.

cjp8200 2년 전 0

1. S -> E 가는 시간 체크(.과 E만 고려)

2. S -> # 가는 시간 체크 (.과 #만 고려하여 맵의 가장 바깥벽 찾기)

3. E-> # 가는 시간 체크 (.과 #만 고려하여 맵의 가장 바깥벽 찾기)

1/2/3을 체크 한 후 1과 2+3 최소 값을 찾게끔 구현하였으나 맞추지 못하였습니다.

어느 부분을 놓쳤는지 도움 부탁드립니다.

#include <stdio.h>
#include <memory.h>

int N, M;
char map[510][510];
int visit[510][510];
int S_y, S_x, E_y, E_x;

int rp, wp;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

struct QUE {
    int r, c, t;
};

struct QUE que[500*500*10];

void IN_QUEUE(int r, int c, int t)
{
    que[wp].r = r;
    que[wp].c = c;
    que[wp].t = t;
    wp++;
}

int BFS(int r, int c)
{
    struct QUE cur;

    IN_QUEUE(r, c, 0);
    visit[r][c] = 1;

    while(rp < wp) {
        cur = que[rp++];
        if (cur.r == E_y && cur.c == E_x) return cur.t-1;
        for (int i=0; i<4; i++) {
            int nr = cur.r + dr[i], nc = cur.c + dc[i];

            if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
            if (visit[nr][nc] == 1) continue;
            if (map[nr][nc] == '.' || map[nr][nc] == 'E') {
                IN_QUEUE(nr, nc, cur.t + 1);
                visit[nr][nc] = 1;
           }
        }
    }

    return 0x7fffffff;
}

int BFS1(int r, int c)
{
    int tmp_t = 0, ans = 0x7fffffff;
    struct QUE cur;

    IN_QUEUE(r, c, 0);
    visit[r][c] = 1;

    while(rp < wp) {
        cur = que[rp++];
        if (cur.r == 0 || cur.r == N-1 || cur.c == 0 || cur.c == M - 1){
            if (ans > cur.t)
                ans = cur.t;
        }
        for (int i=0; i<4; i++) {
            int nr = cur.r + dr[i], nc = cur.c + dc[i];

            if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
            if (visit[nr][nc] == 1) continue;
            if (map[nr][nc] == '.' || map[nr][nc] == '#') {
                if (map[nr][nc] == '.')
                    tmp_t = cur.t + 1;
                else
                    tmp_t = cur.t;

                IN_QUEUE(nr, nc, tmp_t);
                visit[nr][nc] = 1;
           }
        }
    }

    return ans;
}

int main(void)
{
    int ans = 0x7fffffff, ans_s = 0x7fffffff, ans_e = 0x7fffffff;
    int find_s = 0, find_e = 0;

    scanf("%d %d", &N, &M);

    for (int i=0; i<N; i++){
        scanf("%s", &map[i]);
    }

    for (int i=0; i<N; i++){
        for (int j=0; j<M; j++){
            if (map[i][j] == 'S') {
                S_y = i;
                S_x = j;
                find_s = 1;
            }
            else if (map[i][j] == 'E') {
                E_y = i;
                E_x = j;
                find_e = 1;
            }
        }
    }

    ans = BFS(S_y, S_x);    // S -> E

    rp = wp = 0;
    memset(visit, 0, sizeof(visit));

    ans_s = BFS1(S_y, S_x); // S -> #

    rp = wp = 0;
    memset(visit, 0, sizeof(visit));

    ans_e = BFS1(E_y, E_x); // E -> #

    printf("%d %d %d\n", ans, ans_s, ans_e);
    if (find_s == 0 || find_e == 0)
        ans = 0;

    if (ans > ans_s + ans_e)
        ans = ans_s + ans_e;

    printf("%d\n", ans);

    return 0;
}

gumdung 2년 전 0

이 코드가 어떤 점이 잘못되었는지는 모르겠지만

풀고자 하는 방식이 BFS를 사용해서 풀려고 하는 것 같은데

간선의 가중치가 일정하지 않는 그래프에서는 사실상 BFS로 풀기엔 많이 힘든 부분이 존재합니다.

다익스트라 알고리즘을 한번 검색해 보시고 적용해서 풀면 쉽게 풀 수 있으실 겁니다

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

문제

문제

출처

ICPC

[C언어] 틀린 부분이 눈에 보이질 않네요. 고수님들의 도움이 필요합니다.

cjp8200 2년 전 0

gumdung 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말