글 읽기 - 양 3184 BFS 탐색질문

jdouble2037 4년 전 0

42번쨰 줄에서 양 위치 : x : 5, y : 1 값이 뜨네요 어디 제가 bfs 함수에서 탐색을 잘못 도는것인가요...?

1번,2번 테스트 케이스는 옳은 답이나오는데 3번쨰 테스트 케이스는 답이 다르네요.

밑 테스트 케이스에서 0,4에서 BFS 탐색이 시작 될 때 동서남북 순서로 탐색이 진행되는데 탐색중 나올 수 없는 위치가 나오네요 바로 x:5,y:1

양이 있지도 않은 곳에서 42번 조건문이 실행됩니다. 제가 어디를 실수 했을까요.??..

9 12
.###.#####..
#.oo#...#v#.
#..o#.#.#.#.
#..##o#...#.
#.#v#o###.#.
#..#v#....#.
#...v#v####.
.####.#vv.o#
.......####.

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int dx[4] = { 1 , - 1 , 0 , 0};
int dy[4] = { 0 , 0 , -1 , 1};
char map[251][251];
bool visited[251][251];
int R,C;
int total_sheep = 0 , total_wolf = 0;
int livesheep = 0 , livewolf = 0;

queue<pair<int,int>> q;

void BFS()
{
    

    while (!q.empty())
    {
        int y = q.front().first;
        int x = 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 && ny >= 0 && ny < C && nx < R)
            {
                if(map[ny][nx] != '#' && visited[ny][nx] == false)
                {
                
                    if(map[ny][nx] == 'v') { livewolf++;  cout << "늑대 2" <<endl;
                    }
                    if(map[ny][nx] == 'o') { livesheep++;  cout << "양 위치 : " << nx << " " << ny << endl;}
                    visited[ny][nx] = true;
                
                    q.push(make_pair(ny, nx));
                    
                }
                
            }

        
        }
        
    }
    
    if(livewolf == 0 && livesheep == 0)
    {
        
    } else {
    if(livewolf >= livesheep)
    {
        cout << "양 사망 늑대 수 : "<< livewolf << endl;
        livesheep = 0;
          total_wolf += livewolf;
    }
    else
    {
        cout << "늑대 사망" << endl;
        livewolf = 0;
        total_sheep += livesheep;
        
    }
    }
    livewolf = 0; livesheep = 0;
}
int main(void)
{
    cin >> R >> C;
    for(int y = 0; y < C; y++) {
        for(int x = 0; x < R; x++) {
            cin >> map[y][x];
        }
    }
    
    for(int y = 0; y < C; y++) {
        for(int x = 0; x< R; x++){
            if(visited[y][x] == false && map[y][x] != '#')
            {
                cout << y << " "<< x << "실행";
                visited[y][x] = true;
                if(map[y][x] == 'o')
                {
                    livesheep++; cout << "양" << y << " " << x << endl;
                }
                if(map[y][x] == 'v') {
                    livewolf++; cout <<"늑대"<<endl;
                }
                q.push(make_pair(y,x));
                
                BFS();
        
            }
            visited[y][x] = true;

        }
    }
    
    cout << total_sheep << " " << total_wolf << endl;
    
    
}

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

문제

문제

출처

ICPC

양 3184 BFS 탐색질문

jdouble2037 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말