개발자 김수진

[풀이 1]

처음에 시뮬레이션인줄 알고 조건 하나씩 다 따지면서 아래와 같이 구현

#include <iostream>

using namespace std;

//0: 빈칸, 1:벽

int N,M;
int map[50][50];
int dir;
int x,y;
int cnt=0; // number of clean space by robot

//0:북 , 1:동, 2:남, 3:서
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int main(void)
{
    
    cin >> N >> M ;
    cin >> x >> y >> dir;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            cin >> map[i][j];
    }
    
    while(1){
        
        if(map[x][y]==0){
            map[x][y]=2; //현재 위치 청소
            cnt++;
        }
        
        int pdir = dir;
        
        for(int i=0;i<4;i++){
            //왼쪽으로 회전
            if(dir == 0)    dir = 3;
            else    dir-=1;
            
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            
            if(map[nx][ny]==0){ //왼쪽으로 회전했을 때, 청소할 공간이 존재하는 경우
                x = nx; y= ny;
                break;
            }
        }
        
        if(pdir == dir && map[x][y] != 0 ) //후진하는 경우
        {
            x =x-dx[dir];
            y =y-dy[dir];
        }
        
        if(map[x][y] == 1)  break; // 후진했는데 벽인 경우
        
            }
    
    cout << cnt;
    return 0;
    
}

[풀이 2]

맞았습니다가 나왔지만 구글링을 해보니 DFS를 사용하여 재귀함수로 풀 수 있다는 것을 아래와 같이 재귀함수를 사용해서 풀어봤다.

#include <iostream>

using namespace std;

//0: 빈칸, 1:벽

int N,M;
int map[50][50];
int cnt=0; // number of clean space by robot

//0:북 , 1:동, 2:남, 3:서
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};


void DFS(int x , int y, int dir){
    
    map[x][y]=2;

    for(int i=0;i<4;i++){
        
        if(dir == 0)    dir = 3;
        else    dir-=1;
        
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        if(map[nx][ny]==0){
            DFS(nx,ny,dir);
            return;
        }
    }
    /* 후진 하는 경우 */
    x-=dx[dir];
    y-=dy[dir];
    if(map[x][y]==1)    return;
    else    DFS(x,y,dir);

}
int main(void)
{
    int x,y,dir;
    
    cin >> N >> M ;
    cin >> x >> y >> dir;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            cin >> map[i][j];
    }
    
    DFS(x,y,dir);
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            if(map[i][j]==2)    cnt++;
    }
    cout << cnt;
    return 0;
    
}

재귀함수를 사용하여 후진 부분에서 시뮬레이션보다 훨씬 간단하게 풀 수 있었다.

조언, 질문 환영입니다!

댓글 남겨주세요~

#include <iostream>

using namespace std;

int N,M,K;
int map[20][20]={0,};
int x,y;

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

//지도 위 : 1 , 동쪽 : 3 ,
// 처음 주사위 모든 면에 0
// 이동한 칸이 0인 경우 -> 주사위에 있는 숫자가 바닥면으로
// 0이 아닌 경우 -> 주사위로 복사되고 칸은 0으로
int main(void)
{
    cin >> N >> M >> x >> y >> K;
        
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            cin >> map[i][j];
    }
    
    for(int i=0;i<K;i++){
        
        int dir;
        cin >> dir;
        
        int nx = x + dx[dir-1];
        int ny = y + dy[dir-1];
        
        if( nx < 0 || ny <0 || nx >= N || ny >= M)  continue;
        
        int top = dice[1];
        
        if ( dir == 1 ){
            dice[1] =dice[4];
            dice[4] =dice[6];
            dice[6] =dice[3];
            dice[3] =top;
        }
        else if ( dir == 2 ){
            dice[1] =dice[3];
            dice[3] =dice[6];
            dice[6] =dice[4];
            dice[4] =top;
        }
        else if(dir ==3 ){
            dice[1] =dice[5];
            dice[5] =dice[6];
            dice[6] =dice[2];
            dice[2] =top;
        }
        else if(dir ==4 ){
            dice[1] =dice[2];
            dice[2] =dice[6];
            dice[6] =dice[5];
            dice[5] =top;
        }
        
        cout << dice[1] << " ";

        if(map[nx][ny] ==0){
            map[nx][ny] = dice[6];
        }
        else{
            dice[6] = map[nx][ny];
            map[nx][ny] =0;
        }
       
        x = nx;
        y = ny;
    }
        
    return 0;
    
}

1. 이동한 좌표가 범위 내에 있는지 확인 

2. 방향에 알맞게 주사위 움직이기

3. 해당 좌표에 map 값이 0이면 주사위 값을 map에 복사.

0이 아니라면 map 값을 주사위에 복사하고, map을 0으로 초기화

4. 좌표 update

top 부분은  dice[1]로 고정하고 방향에 따라 움직인 뒤 출력해주었다.

index가 헷갈릴까봐 주사위 배열 사이즈를 7로 할당하고 1~6의 index를 사용해서 풀었다.

삼성 기출문제에 비해 비교적 쉽게 풀 수 있는 문제였다.

처음에 아래와 같이 풀었는데 메모리 초과 발생.

아무래도 2차원 배열에 의해서 메모리 초과가 발생한 것 같다.

int형 약 4억 개면 1.6GB 정도 되는데 문제 조건에서는 메모리가 256MB로 제한되어 있다.

#include <iostream>
#include <queue>

using namespace std;

int N,M;
int map[20002][20002]={0,};
int dis[20002]={0,};

int main(void)
{
    queue <int> q;
    int start,end;

    cin >> N >> M;
    for(int i=0;i<M;i++){
        cin >> start >> end;
        map[start][end]=1;
    }
    
    q.push(1);
    dis[1] = 0;
    
    while(!q.empty()){
        start = q.front();
        q.pop();
        
        for(int i=2;i<N+1;i++){
            
            if(dis[i]!= 0) continue;
            if(map[start][i]){
                dis[i] = dis[start]+1;
                q.push(i);
            }
        }
    }
    
    int MAX=0;
    int idx =0;
    int cnt =0;
    
    for(int i=1;i<N+1;i++){
        if(MAX < dis[i]){
            cnt =0;
            MAX = dis[i];
            idx = i;
        }
        if(MAX == dis[i])    cnt++;
    }
    
    cout << idx << " " << dis[idx] << " " << cnt;
    
    return 0;
}

따라서 크기가 고정된 배열 대신 메모리를 동적으로 할당하는 벡터를 사용하였다.

2차원 배열 대신 벡터를 사용하니 메모리 초과가 발생하지 않았다.

#include <iostream>
#include <queue>

using namespace std;

int N,M;
vector <int> map[20001];
int dis[20002]={0,};

int main(void)
{
    queue <int> q;
    int start,end;

    cin >> N >> M;
    for(int i=0;i<M;i++){
        cin >> start >> end;
        map[start].push_back(end);
        map[end].push_back(start);
        
    }
    
    q.push(1);
    dis[1] = 0;
    
    while(!q.empty()){
        start = q.front();
        q.pop();
        
        for(int j=0 ; j<map[start].size();j++){
            if(dis[map[start][j]]!= 0 || map[start][j]== 1) continue;
            dis[map[start][j]] = dis[start]+1;
            q.push(map[start][j]);
            
        }
    }
    
    int MAX=0;
    int idx =0;
    int cnt =0;
    
    for(int i=1;i<N+1;i++){
        if(MAX < dis[i]){
            cnt =0;
            MAX = dis[i];
            idx = i;
        }
        if(MAX == dis[i])    cnt++;
    }
    
    cout << idx << " " << dis[idx] << " " << cnt;
    
    return 0;
}

처음에 아래와 같이 정말 단순하게 풀었더니 시간초과가 나왔다.

생각해보니 input의 개수가 1,000,000 개가 되면 시간이 O(NM)이 되어 시간 초과가 나올 것이다.

#include <iostream>
#include <vector>

using namespace std;

// N : 나무의 수 , M : 집으로 가져가려는 나무의 길이

int N,M;
int tree[1000000]={0,};
int MAX=0;

int main(void)
{
    vector <int> tree;
    
    cin >> N >> M;
    
    for(int i=0;i<N;i++){
        int len;
        
        cin >> len;
        tree.push_back(len);
        if(MAX < tree[i])   MAX = tree[i];
    }
    

    while(MAX >= 0){
        int height=0;
        MAX--;
        
        for(int i=0;i<N;i++){
            if(tree[i] > MAX)   height += tree[i] - MAX;
        }
        
        if(height >= M)  break;
    }
    cout << MAX;
    return 0;
    
}

그래서 알고리즘을 찾아봤다. 이분탐색

#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;
    
}