개발자 김수진

#include <iostream>
#include <vector>

using namespace std;
//Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치
//번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

int N;
int visited[20];
int ability[20][20];
int MIN = 999999999;


void solve()
{
    int s=0;
    int l=0;
    
    for(int i=0;i<N;i++){
        if(visited[i]){
            for(int j=0;j<N;j++){
                if(visited[j])  s += ability[i][j];
            }
        }
        
        else if(!visited[i]){
            for(int j=0;j<N;j++){
                if(!visited[j]) l += ability[i][j];
            }
        }
    }

    int res = s > l ? s-l : l-s;
    if(res < MIN)   MIN =res;
    
}
        
void DFS(int cnt,int idx)
{
    if(cnt == N/2)
    {
        solve();
        return;
    }
    
    for(int i=idx;i<N;i++){
        
            visited[i]=1;
            DFS(cnt+1,i+1);
            visited[i]=0;
        
    }
}

int main(void)
{
    cin >> N ;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)
            cin >>ability[i][j];
    }

    DFS(0,0);
    cout << MIN;
    
    return 0;
}

처음에 solve에서 스타트와 링크 벡터 각각 선언해줘서 

벡터에 insert하고 2중 for 문 각각 2개씩 돌려서 시간초과가 발생한 줄 알았다.

그래서 solve 함수를 visited 배열을 사용해서 2중 for문 하나로 바꿔줘서 제출했는데 또 시간초과

그래서 DFS 부분을 바꿔줬다. 

원래  idx가 없었는데 idx를 추가해줘서 visited가 1인지 확인하는 조건문 없애주고

for문을 idx부터 시작해서 돌리니까 드디어 맞았습니다.

중복 가능, 오름차순

맨 처음에 아무 생각 없이 풀었다가

1 3 1

1 2 1

이런 것들도 가능하게 해서 틀렸다 

DFS 함수에서 재귀할 때 idx 인자를  i로 바꿔주니 맞았다.

#include <iostream>
#include <vector>

using namespace std;

vector <int> v;

int N,M;

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

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

DFS if문에서 return 안해줘서 처음에 답 이상하게 나왔다.

미친거 아닌가

어떻게 return을 빼먹지

#include <iostream>
#include <vector>


using namespace std;

int N,M;
vector <int> v;

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


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

N과 M(1)에서 DFS의 매개변수로 index를 추가해주어 오름차순 조건을 맞춰줬다.

처음에 main에서 DFS 호출할 때 for문 사용해서 결과가 제대로 안나왔는데

진짜 DFS 이해를 아직 제대로 못한 것 같다. 

#include <iostream>

using namespace std;

int N,M;
int visited[8];


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

int main(void)
{
    cin >> N >> M ;

    DFS(0,0);
    return 0;
    
}

보자마자 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;
}