글 읽기 - 도와주세요 문제점은 찾았는데 ㅠ

nicolao00 2년 전 0

왜 틀리는지 잘모르겠습니다... 직접 디버깅해봤는데 두번째 예제에서 맨 위(0밖에 없는 열) 부분에 벽이 안세워지는 문제점이

보이더라구요 근데 코드흐름을 봤을때 그 이유를 도저히 못찾겠습니다 ㅜㅜ

코드에서 잘못된 부분을 좀 찾아주실수있을까요 ? 이틀내내 이거만 잡고있ㅅ브니다 ㅠㅠㅠ

//1906
#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
#define MAX 9
using namespace std;

int matrix[MAX][MAX], copM[MAX][MAX], Y,X, dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0}, ans=0;
bool visited[MAX][MAX];

//감염시켜나가는 bfs알고리즘
void bfs(){
    copy(&matrix[0][0],&matrix[0][0]+X*Y,&copM[0][0]);

    queue<pair<int,int>> que;
    for(int y=0;y<Y;y++){
        for(int x=0;x<X;x++){
            if(copM[y][x]==2) que.push(make_pair(x,y));
        } 
    }    
    
    while(!que.empty()){
        int eX=que.front().first, eY=que.front().second; que.pop();
        for(int i=0;i<4;i++){
            int nX=eX+dx[i], nY=eY+dy[i];
            if(nX>=0 && nX<X && nY>=0 && nY<Y && copM[nY][nX]==0){
                copM[nY][nX]=2; que.push(make_pair(nX,nY));
            }
        }
    }
    
    int temp=0; //마지막에 안전지대 수 구해서 max값이랑 비교
    for(int y=0;y<Y;y++){
        for(int x=0;x<X;x++){
            if(copM[y][x]==0) temp++;
        }
    } if(temp>ans) ans=temp;    
}


// 벽 2개 더 세우는 백트래킹 알고리즘
void dfs(int exX,int exY,int count){
    if(count==2){bfs(); return;}
    for(int y=exY;y<Y;y++){ // 다음에 올 벽이 이전 번째 벽들이 지나왔던 곳들을 지나치지 않게 y=exY로 설정함
        for(int x=0;x<X;x++){
            if(!visited[y][x]&&matrix[y][x]==0){
                visited[y][x]=true; matrix[y][x]=1;
                dfs(x,y,count+1);
                visited[y][x]=false; matrix[y][x]=0;
            }
        }
    }
}


int main(){
    cin>>Y>>X;
    for(int y=Y-1;y>=0;y--){
        for(int x=0;x<X;x++){
            cin>>matrix[y][x];
        }
    }
    //첫번째 세울 벽 찾는 과정
    for(int y1=0;y1<Y;y1++){
        for(int x1=0;x1<X;x1++){
            if(matrix[y1][x1]==0){
                matrix[y1][x1]=1; visited[y1][x1]=true; dfs(x1,y1,0); matrix[y1][x1]=0;
                // 여기서 visited[y1][x1]=ture하는 이유는 2,3번째 벽 세울때 이미 1번째 벽이 지난곳들은 거치지 않도록 하기 위함
            }
        }
    } cout<<ans;
}

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

문제

문제

출처

ICPC

도와주세요 문제점은 찾았는데 ㅠ

nicolao00 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말