개발자 김수진

보자마자 DFS 기본 문제 같았다

근데 당연히 맞을 줄 알았는데 시간초과 나와서 당황했다

알고보니 endl 대신 '\n' 이거 하나  바꿔주니 바로 맞았다.

endl이 시간 많이 잡아먹는듯 하다.

앞으로는 절대 안써야지

#include <iostream>
#include <vector>

using namespace std;

int N,M;
int visited[8];

vector <int> v;

void DFS (int cnt)
{
    if(cnt == M)
    {
        for(int i=0;i<M ;i++)
        {
            cout <<v[i] << " ";
        }
        cout << "\n";
    }
        
    for(int i=0;i<N;i++){
        if(!visited[i]){
            visited[i]=1;
            v.push_back(i+1);
            DFS(cnt+1);
            visited[i]=0;
            v.pop_back();
        }
    }
}

int main()
{
    cin >> N >>M;
    DFS(0);
    return 0;
    
}

#include <iostream>

using namespace std;

//1인 경우는 시계 방향이고, -1인 경우는 반시계 방향
// N극은 0, S극은 1로 나타나있다.

int K; //회전 횟수
int wheel[4][8];
int tmp[4][8];


void rotate(int idx, int dir)
{
    if(dir ==1 ){
        for(int i=0;i<7;i++)
            wheel[idx][i+1] = tmp[idx][i];
        wheel[idx][0] = tmp[idx][7];
    }
    
    else{
        for(int i=1;i<8;i++)
            wheel[idx][i-1] = tmp[idx][i];
        wheel[idx][7] = tmp[idx][0];
    }
}


int check(int idx)
{
    if(idx == 1){
        if(tmp[0][2] == tmp [1][6]) return 0;
        else return 1;
    }
    else if(idx == 2){
        if(tmp[1][2] == tmp[2][6])  return 0;
        else return 1;
    }
    else if (idx ==3){
        if(tmp[2][2] == tmp[3][6])  return 0;
        else return 1;
    }
    
    return 0;
    
}

int main(void)
{
    
    for(int i=0;i<4;i++){
        for(int j=0;j<8;j++)
            scanf("%1d",&wheel[i][j]);
    }
    
    cin >> K;
    
    for(int i=0;i<K;i++){
        
        for(int i=0;i<4;i++){
            for(int j=0;j<8;j++)
                tmp[i][j]=wheel[i][j];
        }
        int idx,dir;
        cin >> idx >> dir;
        idx--;
        
        rotate(idx,dir);
        
        switch(idx)
        {
            case 0:
                while(1){
                    idx++;
                    if(idx == 4)    break;
                    
                    if(dir == 1)    dir =0;
                    else    dir =1;
                    
                    if(check(idx))  rotate(idx,dir);
                    else    break;
                }
                break;
                
            case 1:
                if(check(1)){
                    if(dir == 1)    rotate(0,0);
                    else    rotate(0,1);
                }
                
                while(1){
                    idx++;
                    if(idx == 4)    break;
                    
                    if(dir == 1)    dir =0;
                    else    dir =1;
                    
                    if(check(idx))  rotate(idx,dir);
                    else    break;
                }
                break;
                
            case 2:
                if(check(3)){
                    if(dir == 1)    rotate(3,0);
                    else    rotate(3,1);
                }
                
                while(1){
                    idx--;
                    if(idx == -1)    break;
                    
                    if(dir == 1)    dir =0;
                    else    dir =1;
                    
                    if(check(idx+1))  rotate(idx,dir);
                    else    break;
                }
                break;
                
            case 3:
                while(1){
                    idx--;
                    if(idx == -1)    break;
                    
                    if(dir == 1)    dir =0;
                    else    dir =1;
                    
                    if(check(idx+1))  rotate(idx,dir);
                    else    break;
                }
                break;
        }
    }
    //1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점

    int total=0;
    
    if(wheel[0][0]) total+=1;
    if(wheel[1][0]) total+=2;
    if(wheel[2][0]) total+=4;
    if(wheel[3][0]) total+=8;

    cout << total << "\n";
    
    return 0;
}

한번 풀었던 문제인데 예전에는 '틀렸습니다!'가 나왔지만 이번에는 맞았다.

이렇게 조건 하나씩 따져가면서 직접 다 구현하는 문제를 시뮬레이션이라고 하는 것 같다.

아직 시뮬레이션이 제일 막막하다.

다른 알고리즘들은 방법에 맞게 풀면 될텐데 이거는 하나씩 다 따지는 방법밖에 없으니 조건 잘 따져가면서 풀어야 할듯!

그리고 처음에 input 값 제대로 안따져줘서 틀렸다. 

   Input 값을 cin으로 받아와서 한줄씩 다 받아오기 때문에 에러 발생 

전형적인 BFS 문제로 현재 위치를 기준을 좌,우,상,하를 다 따져보고 조건에 따라 queue에 push

//입력값 잘 구분하기

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

using namespace std;

int map[25][25];
int N;

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

vector <int> v;


int cnt =1;

void BFS(int x ,int y)
{
    cnt++;
    queue <pair<int,int>> q;
    
    q.push(make_pair(x,y));
    map[x][y]=cnt;
    int num=1;
    while(!q.empty()){
        int x1 = q.front().first;
        int y1 = q.front().second;
        
        q.pop();

        for(int i=0;i<4;i++){
            int nx = x1 + dx[i];
            int ny = y1 + dy[i];
            
            if(nx < 0 || nx >= N || ny < 0 || ny >= N)
                continue;
            if(map[nx][ny] == 1){
                q.push(make_pair(nx,ny));
                map[nx][ny] = cnt;
                num++;
            }
        }
    }
    
    v.insert(v.begin()+cnt-2,num);

}

int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf("%1d",&map[i][j]);
        }
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j] == 1)
                BFS(i,j);
        }
    }
    
    sort(v.begin(), v.end());
    cout << v.size() << endl;
    for(int i=0;i<v.size();i++)
        cout << v[i] << endl;
    return 0;
}