백준(boj) 9663, 15684, 17142 - N-Queen, 사다리 조작, 연구소3

문제 링크 - https://www.acmicpc.net/problem/9663 https://www.acmicpc.net/problem/15684 https://www.acmicpc.net/problem/17142

👀문제이해 및 풀이방법

최근 코딩테스트 시즌인데 브루트 포스 문제들을 dp인줄 알고 죽쒀서 브루트포스(완전탐색) 문제를 집중적으로 연습했다 숨도안쉬고 8문제정도를 풀었는데 고생했던 문제들의 체크할 점을 적어두려고 한다.
N-Queen(9663)의 경우 각 놓을 수 있는지 체크할 때 놓는 부분에서 맵 탐색을 통해 Q이 있는 자리들을 체크하면 시간초과가 난다

• 체스판의 대각선위치를 x+y x-y로 체크할 수 있다는 것을 알아놓기
• 일일히 모든 체스판을 돌아다니는 것 보다 Queen의 위치를 저장해놓고 x,y,x+y,x-y로 체크하는게 빠르다 사다리 조작(15684) 삼성문제들의 경우 정말 세심하게 조건을 체크해야한다 놓치는 부분이 생기기 마련이다 어짜피 완전탐색 효율성을 조금 버리더라도 놓지치않고 탐색하도록하자
  
• N+1,N-1,N for문의 끝부분 항상 조심 가장 작을때 항상 체크 연구소3(17142) 정말 너무너무 고생했다 3시간동안 왜안되는건지 모르겠고 모든 반례란 반례는 다 찾아보고 결국 블로그들도 뒤적였지만 어쩜 나랑 똑같다..진짜 스트레스가 극에 달아서 5~6번쯤 틀렸습니다가 뜰때 갑자기 맞았다고 떳다. 왠고 하니 변수초기화를 안해놧다 후 컴파일러상황에따라 로컬컴에서는 자동으로 초기화가 되서 문제가 전혀 없었던것..제발 변수초기화신경쓰자
  
• 모든 것을 다 뒤적여가며 해도 이상할 때에는 사소한 실수를 좀 찾아보자 .. 한 3번을 코드를 갈아엎었는데 그냥 변수초기화 문제였다.

📝코드

N-Queen(9663)

#include <iostream>
#include <vector>
using namespace std;
class nqueen{
private:
    vector<pair<int,int>> queen;
    int N;
    int sol;
public:
    nqueen(){
        std::cin >> N;
        sol=0;
    }
    bool check(int x,int y){
        for(pair<int,int> cur : queen){
            if(cur.first == x || cur.second == y || cur.first+cur.second == x+y || cur.first-cur.second == x-y)
                return false;
        }
        return true;
    };
    void dfs(int x,int y){
        if(!check(x,y))
            return ;
        if(queen.size()==N-1){
            sol++;
            return ;
        }
        for(int i=0;i<N;i++){
            queen.push_back({x,y});
            dfs(x+1,i);
            queen.pop_back();
        }
    }
    void find_sol(){
        for(int i=0;i<N;i++){
            dfs(0,i);
        }
        std::cout << sol <<'\n';
    }
};
int main(){
    nqueen nq;
    nq.find_sol();
    return 0;
}

사다리 조작(15684)

#include <iostream>
#include <vector>
using namespace std;
class ladder{
private:
    vector<vector<int>> map;
    int N,M,H;
public:
    ladder(){
        std::cin >> N >> M >> H;
        map.resize(H,vector<int>(N,0));
        set_val();
    }
    void set_val(){
        int a,b;
        for(int i=0;i<M;i++){
            std::cin >> a >> b;
            a--,b--;
            map[a][b]=1;
            map[a][b+1]=-1;
        }
        // for(int i=0;i<H;i++){
        //     for(int j=0;j<N;j++){
        //         if(map[i][j]==-1)
        //             std::cout << map[i][j];
        //         else
        //             std::cout <<' '<< map[i][j];            
        //     }
        //     std::cout << '\n';
        // }
    }
    bool check(int a){
        int cur=a;
        for(int i=0;i<H;i++)
            cur+=map[i][cur];
        return a==cur;
    }
    bool dfs(int depth,int m,int x,int y){
        if(depth==m){
            for(int i=0;i<N-1;i++){
                if(!check(i))
                    return false;
            }
            return true;
        }
        bool flag=false;
        for(int j=y;j<N-1;j++){
            if(!map[x][j] && !map[x][j+1]){
                map[x][j]=1,map[x][j+1]=-1;
                flag|=dfs(depth+1,m,x,j);
                map[x][j]=0,map[x][j+1]=0;
            }
        }
        for(int i=x+1;i<H;i++){
            for(int j=0;j<N-1;j++){
                if(!map[i][j] && !map[i][j+1]){
                    map[i][j]=1,map[i][j+1]=-1;
                    flag|=dfs(depth+1,m,i,j);
                    map[i][j]=0,map[i][j+1]=0;
                }
            }
        }
        return flag;
    }
    void find_sol(){
        for(int i=0;i<4;i++){
            if(dfs(0,i,0,0)){
                std::cout << i<<'\n';
                return ;
            }
        }
        std::cout << -1 <<'\n';
    }
};
int main(){
    cin.tie(NULL);cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    ladder ld;
    ld.find_sol();   
    return 0;
}

연구소3(17142)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int INF = 1000000000;
struct node{
    int x,y;
    int depth;
};
class laboratory{
private:
    vector<vector<int>> map;
    vector<pair<int,int>> virus;
    int N,M,goal=0,ans=INF;
public:
    laboratory(){
        std::cin >> N >> M;
        map.resize(N,vector<int>(N));
        set_val();
    }
    void set_val(){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                std::cin >> map[i][j];
                if(map[i][j]==0)
                    goal++;
                else if(map[i][j]==2)
                    virus.push_back({i,j});
            }
        }
    }
    void bfs(vector<bool>& start){
        vector<vector<int>> visit=map;
        queue<node> q;
        for(int i=0;i<start.size();i++){
            if(start[i]){
                q.push({virus[i].first,virus[i].second,0});
                visit[virus[i].first][virus[i].second]=3;
            }
        }
        int sol=0,g=0;
        node cur;
        int nx,ny;
        while(!q.empty()){
            cur =q.front();
            q.pop();
            if(map[cur.x][cur.y]!=2)
                sol=max(sol,cur.depth);
            for(int i=0;i<4;i++){
                nx=cur.x+dx[i],ny=cur.y+dy[i];
                if(nx>=0 && nx<N && ny>=0 && ny<N){
                    if(!visit[nx][ny] || visit[nx][ny]==2){
                        if(!visit[nx][ny])
                            g++;
                        visit[nx][ny]=3;
                        q.push({nx,ny,cur.depth+1});
                    }
                }
            }
        }
        if(g==goal)
            ans=min(ans,sol);
    }
    void find_sol(){
        vector<bool> start(virus.size(),false);
        for(int i=0;i<M;i++)
            start[i]=true;
        do{
            bfs(start);
        }while(prev_permutation(start.begin(),start.end()));
        if(ans == INF)
            std::cout << -1 << '\n';
        else
            std::cout << ans << '\n';
    }

};
int main(){
    cin.tie(NULL);cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    laboratory lb;
    lb.find_sol();   
    return 0;
}