글 읽기 - 고수님들 무엇이 문제일까요..?

hesue615 5년 전 0

주어진 예제를 풀고
반례를 찾는 과정에서 찾을 수 없어 이렇게 글 올립니다.

고수님들 도와주세요

#include <cstdio>
#include <utility>
#include <memory.h>
#include <algorithm>
#include <queue>
#define MAX_SIZE 50
#define DIR 4
using namespace std;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int r, c;
int d[MAX_SIZE][MAX_SIZE];
int map[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];
pair<int, int> start, dest;

void init () {
    memset(visited, false, sizeof(visited));
    memset(d, 0, sizeof(d));
}

bool isInRange (int x, int y) {
    bool inRange = true;
    
    if (x < 0 || x >= r) inRange = false;
    if (y < 0 || y >= c) inRange = false;
    if (map[x][y] == -2) inRange = false;
    return inRange;
}

void flooding (int depth) {
    
    for (int i = 0; i < r; ++ i) {
        for (int j = 0; j < c; ++ j) {
            if (map[i][j] == depth) {
                for (int k = 0; k < DIR; ++ k) {
                    int adj_x = i + dx[k];
                    int adj_y = j + dy[k];
                    
                    if (isInRange(adj_x, adj_y) && map[adj_x][adj_y] == 0) {
                        map[adj_x][adj_y] = map[i][j] + 1;
                    }
                }
            }
        }
    }
}

bool bfs (int x, int y) {
    queue<pair<int, int>> q;
    int depth = 0;
    
    visited[x][y] = true;
    q.push(make_pair(x, y));
    
    d[x][y] = 0;
    while(!q.empty()) {
        int cur_x = q.front().first;
        int cur_y = q.front().second;
        q.pop();
        
        if (cur_x == dest.first && cur_y == dest.second) {
            return 1;
        }
        depth ++;
        flooding(depth);
        for (int i = 0; i < DIR; ++ i) {
            int nx = cur_x + dx[i];
            int ny = cur_y + dy[i];
            
            if (!isInRange(nx, ny) || visited[nx][ny]) continue;
            
            if (map[nx][ny] == 0 || map[nx][ny] == -1) {
                visited[nx][ny] = true;
                d[nx][ny] = d[cur_x][cur_y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    } return 0;
}

int main (int argc, char* argv[]) {
    char input;
    
    scanf("%d %d%*c", &r, &c);
    for (int i = 0; i < r; ++ i) {
        for (int j = 0; j < c; ++ j) {
            input = getchar();
            switch (input) {
                case '.':
                    map[i][j] = 0;
                    break;
                case '*':
                    map[i][j] = 1;
                    break;
                case 'X':
                    map[i][j] = -2;
                    break;
                case 'D': {
                    map[i][j] = -1;
                    dest = make_pair(i, j);
                    break;
                }
                case 'S': {
                    map[i][j] = 0;
                    start = make_pair(i, j);
                    break;
                }
                default:
                    break;
            }
        } getchar();
    } init();
    
    if (bfs(start.first, start.second)) {
        printf("%d\n", d[dest.first][dest.second]);
    } else {
        printf("KAKTUS\n");
    }
    return 0;
}

depth를 증가시키는 부분이 잘못됐습니다. 큐에서 원소를 하나 뺄 때마다 depth가 증가하는 것이 아니라, 매 초마다 그 시점에 들어있는 원소들이 모두 빠져나와야 depth가 증가해야 합니다. 예를 들어 3초인 시점에 큐에 원소가 5개 들어있었다면, 5개가 빠져나오는 과정에서 4초, 5초, 6초, 7초, 8초가 흘러가는 것이 아니라 5개가 모두 4초에 처리되어야 합니다.

그리고 지금처럼 매 초마다 맵 전체를 돌면서 물의 위치를 찾는 건 비효율적입니다. 물도 고슴도치와 똑같은 방법으로 bfs를 할 수 있습니다.

hesue615 5년 전 0

친절히 설명해주셔서 정말 감사합니다.

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

문제

문제

출처

ICPC

고수님들 무엇이 문제일까요..?

hesue615 5년 전 0

djm03178 5년 전 1

hesue615 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말