글 읽기 - BFS 를 2번 수행한 코드입니다ㅜㅜ (틀렸습니다)

superm 5년 전 0

먼저 물이 퍼지는 예상시간을 구하는 BFS 탐색을 수행한뒤

고슴도치가 움직이는 BFS 탐색을 수행합니다

만약 예상시간보다 같거나 크면 그 칸으로는 움직일 수 없고 D 를 만나면 거리를 출력하고 종료합니다

제가 생각하기에는 맞는 것 같은데 어디가 틀렸을까요...??

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 51
#define INF 987654321
using namespace std;
typedef pair<int, int> node;

int n,m,ans;
node pre,goal;

char map[MAX][MAX];

int water_dist[MAX][MAX];
bool water_visited[MAX][MAX];

int docci_dist[MAX][MAX];
bool docci_visited[MAX][MAX];

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

vector<node> water;

// 물이 퍼지는 시간을 계산하기 위한 BFS
void bfs_water(){
    queue<node> q;
    for(int i=0; i<water.size(); i++){
        int x = water[i].first;
        int y = water[i].second;
        
        q.push(water[i]);
        water_dist[x][y] = 0;
        water_visited[x][y] = true;
    }
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            
            if(!water_visited[nx][ny] && (map[nx][ny]=='.' || map[nx][ny]=='S')){
                q.push(node(nx,ny));
                water_dist[nx][ny] = water_dist[x][y] + 1;
                water_visited[nx][ny] = true;
            }
        }
    }
}

// 고슴도치가 이동할 수 있는지를 확인하기 위한 BFS
void bfs_docci(){
    queue<node> q;
    q.push(pre);
    docci_dist[pre.first][pre.second] = 0;
    docci_visited[pre.first][pre.second] = true;
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            
            // 아직 방문하지 않았고 비어있는 칸이라면
            if(!docci_visited[nx][ny] && map[nx][ny]=='.'){
                // 이동 후의 시간이 물이 차는 예정 시간 보다 작아야함
                if(docci_dist[x][y] + 1 < water_dist[nx][ny]){
                    q.push(node(nx,ny));
                    docci_dist[nx][ny] = docci_dist[x][y] + 1;
                    docci_visited[nx][ny] = true;
                }
            }
            // 다음 목적지가 비버의 굴이라면
            else if(map[nx][ny] == 'D'){
                cout << docci_dist[x][y] + 1 << "\n";
                return;
            }
        }
    }
    cout << "KAKTUS" << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
            
            if(map[i][j] == '*') water.push_back(node(i,j));
            else if(map[i][j] == 'S'){
                pre.first = i;
                pre.second = j;
            }
            else if(map[i][j] == 'D'){
                goal.first = i;
                goal.second = j;
            }
        }
    }
    
    memset(water_visited, false, sizeof(water_visited));
    memset(docci_visited, false, sizeof(docci_visited));
    
    bfs_water();
    bfs_docci();
}

genesis 5년 전 3

물이 없다면..?

superm 5년 전 0

와...! 무릎을 탁치고갑니다!! 감사합니다

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

문제

문제

출처

ICPC

BFS 를 2번 수행한 코드입니다ㅜㅜ (틀렸습니다)

superm 5년 전 0

genesis 5년 전 3

superm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말