3주차 6월15일 - 6월21일

이번주

항상 세번째 문제가 제일 어려운 것 같다. 매주 세문제만 푼다고 마음을 먹으니 확실히 주중에도 부담이 적고 토요일 하루정도만 시간을 쓰면되서 좋다. 딱 무리하지 않고 감을 익히고 꾸준히 해나갈수 있는 양이라서 좋다. 하지만 확실히 주중에는 안하니, 주말에 첫번째 문제를 풀때는 머리가 좀 멍하다. 

 

이번주의 문제

1. 열쇠

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

9328번: 열쇠

2. 로봇청소기

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

4991번: 로봇 청소기

 

3. 레이저통신

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

6087번: 레이저 통신

문제풀이

1. 상당히 낯선 문제라 시간이 오래 걸렸다. 하지만 결국엔 풀었다!!

 

1) 이차원 벡터 m으로 지도를 입력받았고, visited 벡터로 방문을 체크하는 것까지 보통의 bfs와 같았다. 

2) 애를 먹은 부분은 도착했는데, 문을 못연곳의 위치를 어떻게 처리할지였다. 이 문제는 bfs로 풀지만 거리를 계산하는게 아니다보니 큐에 들어가는 순서는 사실 중요한게 아니다. 

 

그래서

vector<vector<pair<int, int>>> wait('z' - 'a' + 1, vector<pair<int, int>> ());

 

으로 각각의 알파벳에 맞춰서 문을 열쇠가 없어서 문을 안열고 지나간 경우에는 wait에 입력해줬다가, 나중에 열쇠를 찾으면 큐에다가 넣어주었다. 

 

3) 스타팅 포인트도 정해지지 않아서 난관이었다. 시작은

'.'에서도 시작가능하고,

'$'에서도 가능하고,

'소문자' 에서도 가능하고,

'대문자'인 경우에는 열쇠가 있으면 가능하고,

'대문자'인 경우에는 열쇠가 없다가도 열쇠를 찾으면 열수 있다. 

 

이걸 처리할때 로직이 엉켜서 고생을 좀 했다. 

for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                if((i == 0 || i == h-1 || j == 0 || j == w-1)){
                    if(m[i][j] == '.'){
                        start.push(make_pair(i, j));
                    }else if(m[i][j] == '$'){
                        start.push(make_pair(i, j));
                    }else if(m[i][j] >= 'A' && m[i][j] <= 'Z' && keys[m[i][j] - 'A'] == 1){
                        start.push(make_pair(i, j));
                    }else if(m[i][j] >= 'A' && m[i][j] <= 'Z' && keys[m[i][j] - 'A'] == 0){
                        wait[m[i][j]-'A'].push_back(make_pair(i, j));
                    }else if(m[i][j] >= 'a' && m[i][j] <= 'z'){
                        start.push(make_pair(i, j));
                    }
                }
            }
        }

이런식으로 .인 경우, $ 인 경우, 소문자인 경우에는 스타팅 포인트 후보에 바로 입력

대문자인 경우에는 열쇠가 있으면 바로 후보군(start 에 넣음), 

열쇠가 없으면 wait 에 넣어준다

 

이렇게 한다음 

 

이런식으로 스타트 배열을 순환하며 여러 시작점을 체크할때, $로 시작하는 경우는 문서 갯수(cc)를 증가 시키고

열쇠가 없다가(keys[m[sx][sy]-'a'] == 0) 에서 찾게 되면 wait에 있던 것들을 큐에 넣어줘서 다시 탐색할 수 있도록 했다. 

 

그다음부터는 일반적인 bfs와 같았다. 단지 키를 찾을때마다 처리를 해줘야하는 것만 달랐다. 

 

 

했다..

//
//  main.cpp
//  0621SUN_2
//
//  Created by Hayoung Lee on 21/06/2020.
//  Copyright © 2020 Hayoung Lee. All rights reserved.
//

#include <iostream>
#include <vector>
#include <deque>
#include <queue>

using namespace std;

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

int main(int argc, const char * argv[]) {
    cin >> t;
    
    while(t--){
        int h, w;
        cin >> h >> w;
        
        vector<vector<char>> m(h, vector<char> (w)); // map
        vector<vector<int>> visited(h, vector<int> (w, 0)); // 방문 체크
        vector<vector<pair<int, int>>> wait('z' - 'a' + 1, vector<pair<int, int>> ()); // 못연 문의 위치
        queue<pair<int, int>> start;
        vector<int> keys('z' - 'a' + 1, 0);
        
        string temp;
        for(int i = 0; i < h; i++){
            cin >> temp;
            for(int j = 0; j < w; j++){
                m[i][j] = temp[j];
            }
        }
        
        string temp_keys;
        cin >> temp_keys;
        if(temp_keys[0] != '0'){
            for(int i = 0; i < temp_keys.length(); i++){
                keys[temp_keys[i] - 'a'] = 1;
            }
        }
        
        // 시작할 수 있는 곳 후보
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                if((i == 0 || i == h-1 || j == 0 || j == w-1)){
                    if(m[i][j] == '.'){
                        start.push(make_pair(i, j));
                    }else if(m[i][j] == '$'){
                        start.push(make_pair(i, j));
                    }else if(m[i][j] >= 'A' && m[i][j] <= 'Z' && keys[m[i][j] - 'A'] == 1){
                        start.push(make_pair(i, j));
                    }else if(m[i][j] >= 'A' && m[i][j] <= 'Z' && keys[m[i][j] - 'A'] == 0){
                        wait[m[i][j]-'A'].push_back(make_pair(i, j));
                    }else if(m[i][j] >= 'a' && m[i][j] <= 'z'){
                        start.push(make_pair(i, j));
                    }
                }
            }
        }
        
        int cc = 0; //몇개 훔칠수있는지
        while(!start.empty()){
            int sx = start.front().first;
            int sy = start.front().second;
            start.pop();
            
            if(visited[sx][sy] == 1)
                continue;
            
            queue<pair<int, int>> q;
            q.push(make_pair(sx, sy));
            visited[sx][sy] = 1;
            
            if(m[sx][sy] == '$'){
                
                cc++;
                
            }else if(m[sx][sy] >= 'a' && m[sx][sy] <= 'z'){
                if(keys[m[sx][sy]-'a'] == 0){
                    for(int i = 0; i < wait[m[sx][sy]-'a'].size(); i++){
                        q.push(make_pair(wait[m[sx][sy]-'a'][i].first, wait[m[sx][sy]-'a'][i].second));
                    }
                }
                keys[m[sx][sy]-'a'] = 1;
            }
            
            
            while(!q.empty()){
                int x = q.front().first;
                int y = q.front().second;
                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 >= h || ny >= w){
                        continue;
                    }
                    
                    if(m[nx][ny] == '.' && visited[nx][ny] == 0){
                        visited[nx][ny] = 1;
                        q.push(make_pair(nx, ny));
                    }
                    
                    if(m[nx][ny] == '$' && visited[nx][ny] == 0){
                        visited[nx][ny] = 1;
                        q.push(make_pair(nx, ny));
                        cc++;
                    }
                    
                    if(m[nx][ny] >= 'A' && m[nx][ny] <= 'Z' && visited[nx][ny] == 0){
                        //                        문
                        if(keys[m[nx][ny]-'A'] == 1){
                            //                           열쇠 있음
                            visited[nx][ny] = 1;
                            q.push(make_pair(nx, ny));
                        }else if(keys[m[nx][ny]-'A'] == 0){
                            //                             열쇠 없음
                            wait[m[nx][ny]-'A'].push_back(make_pair(nx, ny));
                        }
                    }
                    
                    if(m[nx][ny] >= 'a' && m[nx][ny] <= 'z' && visited[nx][ny] == 0){
                        visited[nx][ny] = 1;
                        q.push(make_pair(nx, ny));
                        if(keys[m[nx][ny]-'a'] == 0){
                            for(int j = 0; j < wait[m[nx][ny]-'a'].size(); j++){
                                visited[wait[m[nx][ny]-'a'][j].first][wait[m[nx][ny]-'a'][j].second] = 1;
                                q.push(make_pair(wait[m[nx][ny]-'a'][j].first, wait[m[nx][ny]-'a'][j].second));
                            }
                        }
                        keys[m[nx][ny]-'a'] = 1;
                    }
                    
                }
            }
        }
        
        cout << cc << "\n";
        
        
    }
    
    
    return 0;
}

 

 

2. 이문제는 못풀었다. bfs를 여러번 실행해주는게 포인트다. 

 

bfs를 실행할때마다 시작하는 포인트를 바꾸어 준다. 

v에는 o, * 인 점들의 위치를 넣어둔다. 

그렇게 해서 o, *1, *2, *3 ....  이렇게 점이 있다면 각 점에서 시작해서 다른 점으로 가는 최단거리를 모두 구할 수 있다. 

즉, o -> *1로 가는 최단거리, o -> *2로 가는 최단거리

그다음에는 *1 -> o로 가는 최단거리, *1 -> *2로 가는 최단거리 ... 을 구할 수 있다. 

dM[i][j]는 v[i] 점을 시작으로 bfs 를 돌렸을때, v[j]로 가는 최단거리를 저장한다. 

 

 

(v배열의 첫번째 값은 반드시 o 인 점을 넣어두고)

v[1] ... v의 마지막 점을 퍼뮤테이션을 해서 어떤 순서로 방문할지에 따라 거리를 구한다. 

o점을 시작으로 v1 -> v2 -> v3 순서로 돌수도 있고, v2 -> v3 -> v1로 돌수도 있으니까.

 

p[i] 는 어떤 점인지를 알려주는거다. 

dM[0][p[0]] 은 0번째 점에서 *인 점들중에 처음으로 방문하는곳까지의 거리

dM[p[i]][p[i+1]] 은 i번째 점에서 그다음점까지의 거리 합이다. 

 

 

되게 어려운 문제였다기 보다는 이런 접근법자체를 경험해보지 못해서 어려웠다. 다음에 비슷한 문제는 잘 풀수 있길

//
//  main.cpp
//  0620SUN_3
//
//  Created by Hayoung Lee on 21/06/2020.
//  Copyright © 2020 Hayoung Lee. All rights reserved.
//

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int w, h;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

vector<vector<int>> bfs(vector<vector<char>> &m, int sx, int sy){
    queue<pair<int, int>> q;
    vector<vector<int>> dist(h, vector<int> (w, -1));
    
    q.push(make_pair(sx, sy));
    dist[sx][sy] = 0;
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        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 >= h || ny >= w){
                continue;
            }
            
            if(m[nx][ny] != 'x' && dist[nx][ny] == -1){
                dist[nx][ny] = dist[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
    
    return dist;
}

int main(int argc, const char * argv[]) {
    while(1){
        cin >> w >> h;
        if(w == 0 && h == 0){
            break;
        }
        
        vector<vector<char>> m(h, vector<char> (w));
        vector<pair<int, int>> v(1);
        
        string temp;
        
        for(int i = 0; i < h; i++){
            cin >> temp;
            for(int j = 0; j < w; j++){
                m[i][j] = temp[j];
                if(m[i][j] == 'o' ){
                    v[0] = make_pair(i, j);
                }else if(m[i][j] == '*'){
                    v.push_back(make_pair(i, j));
                }
            }
        }
        
        int pointSize = (int)v.size();
        vector<vector<int>> dM(pointSize, vector<int> (pointSize)); // o 와 *인 점들 사이의 거리
        bool ok = true;
        for(int i = 0; i < pointSize; i++){
            vector<vector<int>> dist = bfs(m, v[i].first, v[i].second);
            for(int j = 0; j < pointSize; j++){
//                dM[i][j] v[i] 포인트에서 각 포인트로 가는 최단 거리들
//                dist[i번째 포인트의 x][i번째 포인트의 y] i번째 점에서 bfs를 했을때 j로 가는 최단거리
                dM[i][j] = dist[v[j].first][v[j].second];
                
                if(dM[i][j] == -1){
                    ok = false;
                }
            }
        }
        
        if(ok == false){
            cout << -1 << "\n";
            continue;
        }
        
        vector<int> p(pointSize-1);
        for(int i = 0; i < pointSize-1; i++){
            p[i] = i+1;
        }
        
        int ans = -1;
        do{
            int now = dM[0][p[0]];
            for(int i = 0; i < pointSize - 2; i++){
                now += dM[p[i]][p[i+1]];
            }
            if(ans == -1 || ans > now){
                ans = now;
            }
        }while(next_permutation(p.begin(), p.end()));
        cout << ans << "\n";
        
        
    }
    return 0;
}

 

 

3. 이문제는 잘못된 풀이로 시작해서 엄청고생한 문제다. 

결국에는 힌트를 찾아보고 풀었다. 

레이저가 직선으로 닿을 수 있는 모든곳에 대해 거리가 같다고 부여하고, 

직선이 몇개인지를 구한다음 1을빼서 거울갯수를 구하면 되는 간단한 문제이다. 

하지만 가중치를 어떻게 설정할지 헤매서 구하지 못했다. 

 

//
//  main.cpp
//  0621SUN_5
//
//  Created by Hayoung Lee on 21/06/2020.
//  Copyright © 2020 Hayoung Lee. All rights reserved.
//

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

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

int main(int argc, const char * argv[]) {
    cin >> w >> h;
    
    vector<vector<char>> m(h, vector<char> (w));
    vector<vector<int>> visited(h, vector<int> (w, -1));
    vector<pair<int, int>> cs;
    
    string temp;
    for(int i = 0; i < h; i++){
        cin >> temp;
        for(int j = 0; j < w; j++){
            m[i][j] = temp[j];
            if(m[i][j] == 'C'){
                cs.push_back(make_pair(i, j));
            }
        }
    }
    
    queue<pair<int, int>> q;
    q.push(make_pair(cs[0].first, cs[0].second));
    visited[cs[0].first][cs[0].second] = 0;
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        int dist = visited[x][y];
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int nx = x;
            int ny = y;
            while(1){
                nx += dx[i];
                ny += dy[i];
                
                if(nx < 0 || ny < 0 || nx >= h || ny >= w || m[nx][ny] == '*'){
                    break;
                }
                
                if(visited[nx][ny] == -1){
                    visited[nx][ny] = dist + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
    
    cout << visited[cs[1].first][cs[1].second] - 1 << "\n";
    
    return 0;
}

 

 

이번주 느낀점

주중에 바빠서 못보고, 주말에 하루정도 세문제를 풀다보니 확실히 주말에 감이 떨어진 느낌이 없지않아있다. 하지만 꾸준히 하다보면 일주일에 한번해도 감이 남아있을지도! 지금 풀고 있는 bfs문제는 나중에 다시 풀어볼 것이다.