개발자 김수진

[문제]

www.acmicpc.net/problem/13913

[풀이]

수빈이의 위치 N, 동생의 위치 K가 입력으로 주어지고 수빈이가 동생을 찾는 최단경로를 구하는 문제.

이 때, 수빈이는 현재 위치 X 에서 X-1,X+1,2*X로만 움직일 수 있다.

최단경로를 찾아야 하므로 BFS를 사용했다.

현재 위치 X에서  X-1,X+1,2*X로 움직이도록 하였고 visited 배열을 사용해 재방문 하지 않도록 했다.

또한 경로도 구해야 parent 배열을 사용해 해당 index에 오기 전 index 값을 저장했다.

처음의 input의 범위가 0부터 100,000 사이라서 MAX 값을 100,001로 설정하였는데

5001 100000과 같은 경우 

최단 경로를 구하기 위해 100,000을 넘어가는 경우도 있으므로 MAX 값을 200,001로 변경하였다.

[코드]

시간 : 20 ms

#include <iostream>
#include <queue>
#define MAX 200001

using namespace std;

int n[2] = {-1,1};
int visited[MAX]={0,};
int parent[MAX]={0,};
int N,K;
vector <int> ans;

void bfs()
{
    queue<int> q;
    q.push(N);
    
        int idx = q.front();
        q.pop();
        
        if(idx == K ){
            cout << visited[idx] << "\n";
            while(idx != N){
                ans.push_back(idx);
                idx= parent[idx];
            }
            ans.push_back(N);
            return ;
        }
        for(int i=0;i<3;i++){
            int nidx =0;
            if(i==2)    nidx = idx*2;
            else nidx = idx+n[i];
            
            if(nidx < 0 || nidx > MAX || visited[nidx] ) continue;
            
            q.push(nidx);
            visited[nidx]=visited[idx]+1;
            parent[nidx] = idx;
        }
    }

int main(void)
{
    cin >> N >> K;
    bfs();
    int _size = ans.size()-1;
    for(int i=_size; i>=0 ; i--)
        cout << ans[i]<< " ";
    return 0;
}

[문제]

www.acmicpc.net/problem/2589

[풀이]

 두 보물간의 최단거리를 구하는 문제.

최단거리를 구하는 문제이길래 BFS를 사용해서 풀려고 했다.

하지만 보물의 위치가 어딘지 몰라서 시작점과 도착점을 설정하는 데 있어 어려움을 겪었다.

생각해보니 map의 최대 사이즈는 50*50이라서 모든 육지에 대해서 시작점으로 잡고 최단거리를 구해도 되겠다고 생각을 하였다.

따라서 모든 육지에 대해 출발점으로 잡고 BFS 함수에서 최단거리를 구해 그 중에서도 가장 먼 거리를 정답으로 하도록 구현하였다. 

[코드]

시간 : 140ms

#include <iostream>
#include <queue>
#include <cstring>

#define MAX 51

using namespace std;

struct pos{
    int x,y;
};
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

bool map[MAX][MAX]={0,};
int visited[MAX][MAX]={0,};
int N,M;

int BFS(int x,int y)
{
    memset(visited,0,sizeof(visited));
    
    queue <pos> q;
    q.push({x,y});
    visited[x][y]=1;
    int res =0;
    
    while(!q.empty()){
    
        int x= q.front().x;
        int y= q.front().y;
        
        if(res < visited[x][y]) res= visited[x][y];
        
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny]!=0 || map[nx][ny] )  continue;
            
            q.push({nx,ny});
            visited[nx][ny]=visited[x][y]+1;
            
        }
    }
    
    return res;
}

int main(void){
    
    cin >> N >> M;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            char ch;
            cin >> ch;
            if(ch == 'W')   map[i][j]=true;
        }
    }
    
    int ans =0;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(map[i][j]==0){
                int res = BFS(i,j);
                if(res > ans )  ans = res;
            }
        }
    }
    cout << ans-1;
    return 0;
}

[문제]

www.acmicpc.net/problem/5427

[풀이]

매 초마다 불은 상,하,좌,우 방향으로 퍼져 나간다.

이 때 상근이가 탈출하는데 걸리는 시간을 구하는 문제이다.

처음에는 불이 퍼지는 함수랑 상근이가 움직이는 함수를 따로 만들어서 풀었다.

DFS를 사용해 상근이가 움직이도록 했는데, DFS로 움직일 때마다 map을 저장하기 위해 배열을 하나 더 지역변수로 선언했다.

하지만 map의 크기가 워낙 커서 계속 오류가 났다.

두번째 방법으로 BFS 함수에서 불이 퍼지는 것과 상근이가 움직이는 것을 모두 구현했다.

처음에는 불이 퍼지는 것을 그냥 반복문으로 돌면서 불을 만나면 상,하,좌,우로  퍼지도록 구현했다.

하지만 시간초과가 나와서 불이 퍼지는 것도 BFS로 queue를 사용해 풀었다.  

불이 퍼지고 상근이가 움직이는 것을 구현하기 위해  queue의 size만큼 while문을 반복하도록 구현하였다. 

[코드]

시간 : 176ms

#include <iostream>
#include <cstring>
#include <queue>

#define MAX 1001

using namespace std;

struct pos{
    int x,y;
};

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

pos start;
int visited[MAX][MAX]={0,};
int map[MAX][MAX]={0,};
int w,h;
int res=0;

queue <pos> fq;

void BFS()
{
    queue <pos> q;
    
    q.push(start);
    visited[start.x][start.y]=1;
    
    while(!q.empty()){
        
        int _size = q.size();
        int fsize = fq.size();
        
        while(fsize--){
            int x = fq.front().x;
            int y = fq.front().y;
            
            fq.pop();
            
            for(int i=0;i<4;i++){
                
                int nx = x+dx[i];
                int ny = y+dy[i];
                
                if(nx<0 || ny<0 || nx>=w || ny >= h || map[nx][ny]!= 0 || visited[nx][ny] != 0)  continue;

                map[nx][ny]=1;
                visited[nx][ny]=-1;
                fq.push({nx,ny});
            }
        }
        
        while(_size--){
        
            int x = q.front().x;
            int y = q.front().y;
            
            q.pop();
            
            for(int i=0;i<4;i++){
                
                int nx = x+dx[i];
                int ny = y+dy[i];
                
                if(nx<0 || ny<0 || nx>=w || ny >= h){
                    res = visited[x][y];
                    return;
                }
                
                if(map[nx][ny]!= 0 || visited[nx][ny]!=0)  continue;

                visited[nx][ny]=visited[x][y]+1;
                q.push({nx,ny});
                            
            }
        }
    }
}


int main(void)
{
    int T;
    cin >> T;
    
    for(int k=0;k<T;k++)
    {
        memset(visited, false, sizeof(visited));
        memset(map, false, sizeof(map));

        while(!fq.empty())  fq.pop();
        
        cin >> h >> w;
        res=0;
        
        for(int i=0;i<w;i++){
            for(int j=0;j<h;j++){
                
                char ch;
                cin >> ch;
                
                if( ch == '@')  start={i,j};
                else if( ch == '*') {
                    map[i][j]=1;
                    visited[i][j]=-1;
                    fq.push({i,j});
                }
                else if( ch == '#') map[i][j]=1;
                
            }
        }
        
        BFS();
        
        if(res==0)  cout << "IMPOSSIBLE";
        else    cout << res;
        
        cout << "\n";
    }
    
    return 0;
}

[문제]

www.acmicpc.net/problem/2146

[풀이]

섬을 연결하는 다리를 설치할 수 있는데, 가장 짧은 다리 하나를 설치할 수 있다.

이 때 가장 짧은 다리의 길이를 구하는 문제.

처음에는 섬을 분리하여, 섬의 가장자리에서 다른 섬의 가장자리로의 최단 거리를 구하려고 했다.

생각해보니 가장자리를 따로 구하지 않고 ,

BFS를 통해 최단 거리를 구하면 하나의 섬의 가장자리에서 다른 섬의 가장자리까지의 거리가 된다. 

따라서 DFS 함수에서 각 섬을 구분하고, BFS 함수에서 섬 간의 최단거리를 구했다.

BFS에서 최단거리를 구할 때 시작섬의 좌표를 queue에 모두 넣어줬다.

그리고 하나씩 pop하여 상,하,좌,우 방향으로 퍼져나갔다.

이 때 다른 섬을 만나면 거리를 return 하면서 BFS 함수를 종료하였다. 

이와 같은 방식으로 첫번째 섬부터 마지막 섬까지 반복하여  가장 짧은 다리의 길이를 구할 수 있다. 

[코드]

시간 : 44ms

#include <iostream>
#include <queue>
#define MAX 101

using namespace std;

struct pos{
    int x,y;
};

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int map[MAX][MAX]={0,};
bool tmp[MAX][MAX]={0,};
int N;
int cnt=0;
int answer=MAX*MAX;

void DFS(int x, int y,int cnt)
{
    map[x][y]=cnt;
    tmp[x][y]=true;
    
    for(int i=0;i<4;i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx<0 || ny <0 || nx >= N || ny >= N || tmp[nx][ny] || map[nx][ny]==0 )  continue;
        
        DFS(nx,ny,cnt);
    }
}

int BFS(int idx)
{
    int visited[MAX][MAX]={0,};
    queue <pos> q;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j]==idx){
                q.push({i,j});
                visited[i][j]=1;
            }
        }
    }
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        q.pop();

        for(int k=0;k<4;k++){
            int nx = x+dx[k];
            int ny = y+dy[k];
            
            if(nx<0 || ny <0 || nx >= N || ny >= N || visited[nx][ny]!=0 )  continue;
            if(map[nx][ny] !=0 &&  map[nx][ny] != idx)  return visited[x][y]+1;
            
            visited[nx][ny]=visited[x][y]+1;
            q.push({nx,ny});
        }
    }
    return 0;
}


int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin >> map[i][j];
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j]==1 && !tmp[i][j]){
                cnt++;
                DFS(i,j,cnt);
            }
        }
    }
    
    for(int i=1;i<cnt;i++)  {
        int res =BFS(i);
        if(res!=0 && res < answer)  answer =res;
    }
    cout << answer-2;
    return 0;
}

[문제]

www.acmicpc.net/problem/1937

[풀이]

판다는 대나무를 다 먹어 치우면 상,하,좌,우 중 하나로 이동할 수 있다.

단, 이전에 먹었던 대나무보다 많은 대나무가 존재하는 곳으로만 이동할 수 있다.

판다가 최대한 살 수 있는 일수를 구하면 된다.

DP 배열에 해당 위치에서 이동할 수 있는 최대 거리를 저장했다.

따라서 DFS 함수를 통해 미리 DP 배열의 값을 구해놨다면 DP 배열에 저장된 값을 return  하면 된다.

아직 DP 배열에 0이 저장되어 있다면 다시 DFS 함수를 호출하여 해당 좌표에서 가장 멀리 갈 수 있는 거리를 구하면 된다.

아래 코드와 같이 DFS 함수를 통해 (1,1) ~ (N,N)까지 해당 좌표에서 가장 멀리 갈 수 있는 거리를 구하여 최댓값을 구하면 된다. 

[코드]

시간 : 128ms

#include <iostream>
#include <algorithm>
#define MAX 501

using namespace std;

int DP[MAX][MAX]={0,};
int map[MAX][MAX]={0,};
int dx[4] ={-1,1,0,0};
int dy[4] ={0,0,-1,1};
int res=0;
int N;


int DFS(int x, int y)
{
    if(DP[x][y])   return DP[x][y];
    DP[x][y] =1;
    
    for(int i=0;i<4;i++){
        
        int nx= x+dx[i];
        int ny= y+dy[i];
        
        if(nx < 0 || ny <0 || nx >= N || ny >= N)   continue;
        if(map[nx][ny] <= map[x][y])    continue;
        
        DP[x][y] = max(DP[x][y] , DFS(nx,ny)+1);
        

    }
    return DP[x][y];
}


int main(void)
{
    
    cin >> N;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin >> map[i][j];
        }
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            res = max(res , DFS(i,j));
        }
    }
    cout << res;
    
    return 0;
    
}

[문제]

www.acmicpc.net/problem/13459

[풀이]

보드의 정보가 입력으로 주어지고 , 10번 이하의 움직임으로 빨간공이 빠져나갈 수 있으면 1을 출력하고 없으면 0을 출력한다.

먼저 입력으로 보드의 크기와 상태를 입력받았다.

장애물인 있는 좌표는 map에 -1을 저장하고, 구멍이 존재하는 좌표는 1을 저장했다.

DFS를 사용해서 풀었다. DFS 함수에서 인자 값으로 몇 번 움직였는지를 나타내는 cnt 를 넘겨주었다.

문제 조건에 의해 cnt가 10보다 크거나 같다면  return false를 하여 DFS 함수를 끝냈다.

DFS 함수에서는 for문을 통해 상,하,좌,우로 움직일 수 있도록 하였다. 

solve 함수는 공을 움직이는 함수로 인자로 전달받은 dir 방향으로 움직이도록  하였다.

문제의 조건들을 잘 신경써야 될 것 같다.

Ex )

1. 빨간공과 파란공 모두 탈출하면 실패

2. 파란공이 먼저 탈출하면 실패 

3. 보드의 한 칸에는 하나의 공만 존재할 수 있음

[코드]

시간 : 24ms

#include <iostream>
#define MAX 11

using namespace std;


struct pos{
    int x,y;
};

pos R,B;

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

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

int solve(int dir)
{
    int rx = R.x;
    int ry = R.y;
    
    while(1){
        if(map[rx][ry] != 0)    break;
        rx += dx[dir];
        ry += dy[dir];
    }
    
    int bx = B.x;
    int by = B.y;

    while(1){
        if(map[bx][by] != 0)    break;
        bx += dx[dir];
        by += dy[dir];
    }
    
    if(map[rx][ry] == 1 && map[bx][by] != 1)    return 1;
    else if(map[bx][by] == 1)   return -1;
    
    rx-= dx[dir];
    ry-= dy[dir];
    
    bx -= dx[dir];
    by -= dy[dir];
    
    if(rx == bx && ry == by){
        if(dir == 0 ) R.x > B.x ? rx++ : bx++ ;
        else if (dir == 1) R.y > B.y ? by-- : ry--;
        else if(dir == 2)   R.x > B.x ? bx-- : rx--;
        else if(dir == 3)   R.y > B.y ? ry++ : by++;

    }
    
    R={rx,ry};
    B={bx,by};
    
    return 0;
}

int DFS(int cnt)
{
    if(cnt >= 10 )  return 0;
    
    for(int i=0;i<4;i++){
        
        pos tmp_R = R;
        pos tmp_B = B;
        
        int res = solve(i);
        
        if(res==1 ) return 1;
        else if(res == -1)  continue;
        
        if(DFS(cnt+1) == 1)  return 1;
        
        R = tmp_R;
        B = tmp_B;
    }
    return -1;
}

int main(void)
{
    cin >> N >> M ;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            char ch;
            cin >> ch;
            
            if (ch == '#')  map[i][j]=-1;
            else if(ch == 'O')  map[i][j] = 1;
            else if(ch == 'R')  {
                R.x = i;
                R.y = j;
            }
            else if(ch == 'B')  {
                B.x = i;
                B.y = j;
            }
        }
    }
    
    if(DFS(0) == 1) cout << "1";
    else cout << "0";
    
    return 0;
    
}

[문제]

www.acmicpc.net/problem/1744

[풀이]

길이가 N인 수열이 주어지고 수열의 합의 최댓값을 구하는 문제.

숫자끼리 서로 묶어서 곱하여 더할 수 있다.

단 모든 수는  한번만 묶거나, 묶지 않아야한다.

큰 수 끼리 곱할수록 값이 더 커지므로 처음에는 vector만 사용해서 풀었다.

음수, 양수를 따로 벡터에 저장한 뒤 정렬하여 풀었는데 틀렸습니다가 나오길래 priority_queue를 사용해서 풀었다.

priority_queue는 기본적으로 오름차순 정렬을 하고 , greater를 붙일 경우 내림차순으로 정렬한다.

음수, 양수를 각각 negative, positive 큐에 저장하고 두개씩 빼서 서로 곱하여 더해준다. 

따라서 queue의 크기가 홀수이면 안되므로 , 홀수일 경우 1을 push하여 짝수 개로 맞춰준다. 

음수에 0을 곱할 경우 더 큰 값을 얻을 수 있다. 

따라서 0이 존재한다면 1 대신에 0을 negative에 push 하였다.

[코드]

시간 : 0ms

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

#define MAX 10001
using namespace std;



int main(void)
{
    int N;
    int sum=0;
    int cnt =0;
    
    priority_queue <int,vector<int>,greater<int>> positive;
    priority_queue <int> negative;


    cin >> N;
    for(int i=0;i<N;i++){
        int num;
        cin >> num;
        
        if(num == 1)    sum+=1;
        else if(num == 0)   cnt++;
        else if (num > 0 )  positive.push(num);
        else negative.push(num);
    }
    
    if(positive.size()%2 != 0)  positive.push(1);
    if(negative.size()%2 != 0)  {
        if(cnt != 0)    negative.push(0);
        else    negative.push(1);
    }
    
    while(!positive.empty()){
        int num1 = positive.top();
        positive.pop();
        int num2 = positive.top();
        positive.pop();
        
        sum += num1*num2;
    }
    while(!negative.empty()){
        int num1 = negative.top();
        negative.pop();
        int num2 = negative.top();
        negative.pop();
        
        sum += num1*num2;
    }
    
    cout << sum;
    return 0;
}

[문제]

www.acmicpc.net/problem/2638

[풀이]

모눈종이 위에 치즈가 존재하고 , 치즈가 공기와 접촉하는 변이 2개 이상일 경우 한시간 뒤에 녹게된다.

(치즈 내부에 있는 치즈 공간은 공기와 접촉하지 않는 것으로 가정한다. )

이 때 치즈가 모두 녹는데 걸리는 시간을 구하는 문제이다.

BFS를 사용해 외부 공간을 queue에 저장하였다.

queue에서 하나씩 pop 할 때마다 해당 좌표의 상하좌우 중에서 치즈가 존재하는지 확인한다.

치즈가 존재한다면 , 치즈가 존재하는 좌표의 visited 배열 값을 +1 해준다.

위와 같이 반복하여 while문을 나왔을 때, visited 배열의 값이 2 이상인 경우 접촉하는 변이 2개 이상인 경우이므로 

해당 좌표 map 배열의 값을 0으로 update 해준다. 

[코드]

시간 : 8ms

#include <iostream>
#include <queue>
#define MAX 101

using namespace std;

struct pos{
    int x,y;
};

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

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

bool BFS()
{
    bool flag= false;
    
    int visited[MAX][MAX]={0,};
    
    queue <pos> q;
    q.push({0,0});
    visited[0][0]=-1;
    
    while(!q.empty()){
        
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx<0 || ny < 0 || nx >= N || ny >= M)    continue;
            if(map[nx][ny] == 1){
                visited[nx][ny]++;
                continue;
            }
            if(visited[nx][ny]!=0)  continue;
            
            q.push({nx,ny});
            visited[nx][ny] = -1;
            
        }
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(visited[i][j] >= 2){
                map[i][j] = 0;
                flag = true;
            }
        }
    }
    
    return flag;
}

int main(void)
{
    cin >> N >> M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)    cin >> map[i][j];
    }
    
    int cnt =0;
    
    while(1){
        if(BFS()==false)    break;
        cnt++;
    }
    
    cout << cnt;
    return 0;
    
}