2주차 6월8일 - 6월14일

이번주

저번주에 3문제를 풀어봤더니 딱 밸런스 잘 맞는거같다. 한동안 요정도로 계속 해봐야겠다. 

이번주의 문제

1. 물통:

https://www.acmicpc.net/problem/2251

2251번: 물통

 

2. 숨박꼭질:

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

3. 탈옥: 

https://www.acmicpc.net/problem/9376

9376번: 탈옥

 

문제풀이

 

1. 물통: 

 

완전 풀이를 헛다리 짚었다. visited에 기록할 정보가 낯설때마다 이런 실수를 반복중. map을 잘못이용해서 메모리 초과가 나게 되버렸다. 하지만 단순이 이차원행렬(많아도 3차원 행렬으로 vistited정보를 찾을 수 있는 문제.

 

나쁜 틀린 코드!!!!

//
//  main.cpp
//  0603SAT
//
//  Created by Hayoung Lee on 13/06/2020.
//  Copyright © 2020 Hayoung Lee. All rights reserved.
//

#include <iostream>
#include <map>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;


// a, b 의 물양만 알면 c는 구할수 잇다.
map<char, int> size;  //count: key가 존재하면 1 아니면 0을 반환하게됨.
map<string, int> visited;
vector<int> answer;

typedef struct water{
    int a;
    int b;
    int c;
} w;

string water2string(water w){
    return to_string(w.a) + "," + to_string(w.b) + "," + to_string(w.c);
}

int main(int argc, const char * argv[]) {
    cin >> size['a'];
    cin >> size['b'];
    cin >> size['c'];
    
    queue<w> q;
    q.push({0, 0, size['c']});
    visited[water2string(q.front())] = 1;
    
    while(!q.empty()){
        w nw = q.front();
        q.pop();
        
        if(nw.a == 0){
            answer.push_back(nw.c);
        }
        
        
        if(nw.a != 0){
            w next;
            if(size['b'] - nw.b > nw.a){
//          b의 남은 부분이 a의 총량보다 많은 경우 -> nw.a를 다 옮긴다
                next = {0, nw.b + nw.a, nw.c};
//                cout << "here 1:" << water2string(next) << "\n";
            }else if(size['b'] - nw.b > 0){
//          b의 남은 부분이 a의 총량보다 적은 경우 -> b를 꽉 채운다
                next = {nw.a - (size['b'] - nw.b), size['b'], nw.c};
//                cout << "here 2:" << water2string(next) << "\n";
            }
            if(visited.count(water2string(next)) == 0){
                visited[water2string(next)] = 1;
                q.push(next);
            }

            if(size['c'] - nw.c > nw.a){
            //c의 남은 부분이 a의 총량보다 많다 -> nw.a를 다옮긴다.
                next = {0, nw.b, nw.c + nw.a};
//                cout << "here 3:" << water2string(next) << "\n";
            }else if(size['c'] - nw.c > 0){
                next = {nw.a - (size['c'] - nw.c), nw.b, size['c']};
//                cout << "here 4:" << water2string(next) << "\n";
            }
            if(visited.count(water2string(next)) == 0){
                visited[water2string(next)] = 1;
                q.push(next);
            }
        }
        
        if(nw.b != 0){
            w next;
//            b->a
            if(size['a'] - nw.a > nw.b){
                next = {nw.a + nw.b, 0, nw.c};
//                cout << "here 5:" << water2string(next) << "\n";
            }else if(size['a'] - nw.a > 0){
                next = {size['a'], nw.b - (size['a'] - nw.a), nw.c};
//                cout << "here 6:" << water2string(next) << "\n";
            }
            if(visited.count(water2string(next)) == 0){
                visited[water2string(next)] = 1;
                q.push(next);
            }
//        b-> c
            if(size['c'] - nw.c > nw.b){
                //c의 남은 부분이 a의 총량보다 많다 -> nw.a를 다옮긴다.
                next = {nw.a, 0, nw.b + nw.c};
//                cout << "here 7:" << water2string(next) << "\n";
            }else if(size['c'] - nw.c > 0){
                next = {nw.a, nw.b - (size['c'] - nw.c), size['c']};
//                cout << "here 8:" << water2string(next) << "\n";
            }
            if(visited.count(water2string(next)) == 0){
                visited[water2string(next)] = 1;
                q.push(next);
            }
           
        }
        
        if(nw.c != 0){
              w next;
//            c -> a
            if(size['a'] - nw.a > nw.c){
                next = {nw.a + nw.c, nw.b, 0};
//                cout << "here 9:" << water2string(next) << "\n";
            } else if(size['a'] - nw.a > 0){
                next = {size['a'], nw.b , nw.c - (size['a'] - nw.a)};
//                cout << "here 10:" << water2string(next) << "\n";
            }
            if(visited.count(water2string(next)) == 0){
                visited[water2string(next)] = 1;
                q.push(next);
            }
//            c -> b
            if(size['b'] - nw.b > nw.c){
                next = {nw.a, nw.b + nw.c, 0};
//                cout << "here 11:" << water2string(next) << "\n";
            }else if(size['b'] - nw.b > 0){
                next = {nw.a, size['b'], nw.c - (size['b'] - nw.b)};
//                cout << "here 12:" << water2string(next) << "\n";
            }
            if(visited.count(water2string(next)) == 0){
                visited[water2string(next)] = 1;
                q.push(next);
            }
        }
    }
    
    sort(answer.begin(), answer.end());
    answer.erase(unique(answer.begin(), answer.end()), answer.end());
    for(int i = 0; i < answer.size(); i++){
        cout << answer[i] << " ";
    }
    
    return 0;
}

 

 

푼것: 바꾼건 visited를 어떻게 활용하나였다. 위의 코드는 a, b, c를 다 저장하는거라 메모리 초과인데, ab만 저장해서 메모리를 줄였다. 물을 이동하는걸 더 일반화하면 좋지만, 아직 나는 이렇게 길게 코드를 쓰면서 연습을 하는 단계인것 같다.  

//
//  main.cpp
//  0603SAT
//
//  Created by Hayoung Lee on 13/06/2020.
//  Copyright © 2020 Hayoung Lee. All rights reserved.
//

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int size[3];
int visited[201][201];
vector<int> answer;
queue<pair<int, int>> q;


int main(int argc, const char * argv[]) {
    cin >> size[0] >> size[1] >> size[2];
    int s = size[2];
    
    visited[0][0] = 1;
    q.push(make_pair(0, 0));
    
    while(!q.empty()){
        int na = q.front().first;
        int nb = q.front().second;
        int nc = s - na - nb;
        q.pop();
        
        if(na == 0){
            answer.push_back(s - na - nb);
        }

        if(na != 0){
            if(na+nb <= size[1] && visited[0][na+nb] == 0){
                visited[0][na+nb] = 1;
                q.push(make_pair(0, na+nb));
            }
            
            if(na+nb > size[1] && visited[na - (size[1] - nb)][size[1]] == 0){
                visited[na - (size[1] - nb)][size[1]] = 1;
                q.push(make_pair(na - (size[1] - nb),size[1]));
            }
            
           if(na+nc <= size[2] && visited[0][nb] == 0){
               visited[0][nb] = 1;
               q.push(make_pair(0, nb));
           }
           
           if(na+nc > size[2] && visited[na - (size[2] - nc)][nb] == 0){
               visited[na - (size[2] - nc)][nb]  = 1;
               q.push(make_pair(na - (size[2] - nc), nb));
            }
        }
        
        if(nb != 0){
            if(na+nb <= size[0] && visited[na+nb][0] == 0){
                visited[na+nb][0] = 1;
                q.push(make_pair(na+nb, 0));
            }
            
            if(na+nb > size[0] && visited[size[0]][nb - (size[0] - na)] == 0){
                visited[size[0]][nb - (size[0] - na)] = 1;
                q.push(make_pair(size[0],nb - (size[0] - na)));
           }
           
           if(nb+nc <= size[2] && visited[na][0] == 0){
               visited[na][0] = 1;
               q.push(make_pair(na, 0));
           }
           
           if(nb+nc > size[2] && visited[na][nb - (size[2] - nc)] == 0){
               visited[na][nb - (size[2] - nc)]  = 1;
               q.push(make_pair(na, nb - (size[2] - nc)));
          }
        }
        
        if(s - na - nb != 0){
            if(na+nc <= size[0] && visited[na+nc][nb] == 0){
                visited[na+nc][nb] = 1;
                q.push(make_pair(na+nc, nb));
            }
            
            if(na + nc > size[0] && visited[size[0]][nb] == 0){
                visited[size[0]][nb] = 1;
                q.push(make_pair(size[0], nb));
            }
            
            if(nb+nc <= size[1] && visited[na][nb+nc] == 0){
                visited[na][nb+nc] = 1;
                q.push(make_pair(na, nb+nc));
            }
            
            if(nb + nc > size[1] && visited[na][size[1]] == 0){
                visited[na][size[1]] = 1;
                q.push(make_pair(na, size[1]));
            }
        }
    }
    
    
    sort(answer.begin(), answer.end());
    answer.erase(unique(answer.begin(), answer.end()), answer.end());
    for(int i = 0; i < answer.size(); i++){
        cout << answer[i] << " ";
    }
    
    return 0;
}

 

 

2. 숨박꼭질 2.

이 문제는 낮은 정답률에 비해선 별게 아니었다. 

1) visited를 모두 -2로 초기화

2) 방문 안한거면 기본적인 bfs문제 풀이처럼 큐에 넣어주었고, 

방문한거라도, visited값이 같으면 경우만 다르지 도달하는 카운트는 같았으니까 큐에 넣어준다. 

//
//  main.cpp
//  0603SAT_2
//
//  Created by Hayoung Lee on 13/06/2020.
//  Copyright © 2020 Hayoung Lee. All rights reserved.
//

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int lim = 100000;
int n, k;

int main(int argc, const char * argv[]) {
    int visited[lim * 2 + 1];
    queue<int> q;
    
    for(int i = 0; i <= lim * 2; i++){
        
        visited[i] = -2;
    }
    
    cin >> n >> k;
    visited[n] = 0;
    q.push(n);
    int answer = 0;
//    int mmin = -1;
    
    while(!q.empty()){
        int nn = q.front();
        q.pop();
        
        if(nn == k){
//            cout << visited[nn];
            if(answer == 0){
                cout << visited[nn] << "\n";
            }
            answer++;
        }
        
        if(nn - 1 >=0 && (visited[nn-1] == -2 || visited[nn - 1] == visited[nn] + 1) ){
            visited[nn-1] = visited[nn] + 1;
            q.push(nn-1);
        }
//
//        if(nn - 1 >= 0 && visited[nn - 1] == visited[nn] + 1){
//
//        }

        if(nn + 1 <= lim * 2 && (visited[nn + 1] == -2 || visited[nn + 1] == visited[nn] + 1) ){
            visited[nn+1] = visited[nn] + 1;
            q.push(nn+1);
        }

        if(nn * 2 <= lim * 2 && (visited[nn * 2] == -2 || visited[nn * 2] == visited[nn] + 1)){
            visited[nn * 2] = visited[nn] + 1;
            q.push(nn * 2);
        }
    }
    
    cout << answer << "\n";

    return 0;
}

 

 

 

3. 탈옥

못풀었다. 이상하게 저번주도 세번째 문제는 손도 못댔는데 이번주도 이러네. 

보통의 bfs와는 다르게 시작점이 여러개인 문제였다. 시작점이 여러개인 문제를 어떻게 해결할 수 있을지 지식을 주워들은 문제. 

bfs관련 문제 풀었던것 나중에 다시 한번 다 풀어야할것 같다. 

* 덱을 사용해서 가중치가 없는것 있는것을 구분하는것이 포인트

//
//  main.cpp
//  0603SAT_3
//
//  Created by Hayoung Lee on 13/06/2020.
//  Copyright © 2020 Hayoung Lee. All rights reserved.
//

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <algorithm>
using namespace std;

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

vector<vector<int>> bfs(vector<vector<char>> &arr, int x, int y, int h, int w){
//    숫자 반환
    vector<vector<int>> visited(h,vector<int>(w, -1));
    
    visited[x][y] = 0;
    deque<pair<int, int>> dq;
    dq.push_back(make_pair(x,y));

    while(!dq.empty()){
        int nx = dq.front().first;
        int ny = dq.front().second;
        dq.pop_front();

        for(int i = 0; i < 4; i++){
            int next_x = nx + dx[i];
            int next_y = ny + dy[i];

            if(next_x < 0 || next_y < 0 || next_x >= h || next_y >= w){
                continue;
            }

            if(visited[next_x][next_y] == -1 && (arr[next_x][next_y] == '.' || arr[next_x][next_y] == '$') ){
                dq.push_front(make_pair(next_x, next_y));
                visited[next_x][next_y] = visited[nx][ny];
            }
            if(visited[next_x][next_y] == -1 && arr[next_x][next_y] == '#'){
                dq.push_back(make_pair(next_x, next_y));
                visited[next_x][next_y] = visited[nx][ny] + 1;
            }
        }
    }

    return visited;
}

int main(int argc, const char * argv[]) {
    int ca;
    cin >> ca;
  
    while(ca--){
        int h, w;
        cin >> h >> w;
        
        vector<vector<char>> arr(h+2,vector<char>(w+2, '.'));
        vector<pair<int, int>> v;
        
        string temp;
        for(int i = 1; i < h+1; i++){
            cin >> temp;
            for(int j = 1; j < w+1; j++){
                arr[i][j] = temp[j-1];
                if(arr[i][j] == '$'){
                    v.push_back(make_pair(i, j));
                }
            }
        }
        
        vector<vector<int>> d0 = bfs(arr, 0, 0, h+2, w+2);
        vector<vector<int>> first = bfs(arr, v[0].first, v[0].second, h+2, w+2);
        vector<vector<int>> second = bfs(arr, v[1].first, v[1].second, h+2, w+2);
        
        vector<int> answer;
        for(int i = 0; i < h+2; i++){
            for(int j = 0; j < w+2; j++){
                if((arr[i][j] == '.' || arr[i][j]== '$' )&& d0[i][j] != -1 && first[i][j] != -1 && second[i][j] != -1){
                    answer.push_back(d0[i][j] + first[i][j] + second[i][j]);
                }
                
                if(arr[i][j] == '#' && d0[i][j] != -1 && first[i][j] != -1 && second[i][j] != -1){
                    answer.push_back(d0[i][j] + first[i][j] + second[i][j] - 2);
                }
            }
        }
        
        sort(answer.begin(), answer.end());
        cout << answer[0] << "\n";
        
        
//        cout << "\n";
//
//        for(int i = 0; i < h+2; i++){
//            for(int j = 0; j < w+2; j++){
//                cout << first[i][j];
//            }
//            cout << "\n";
//        }
        
//        for(int i = 0; i < h+2; i++){
//            for(int j = 0; j < w+2; j++){
//                cout << d0[i][j];
//            }
//            cout << "\n";
//        }


        
    }
    
    
    
    
    return 0;
}