반응형

문제풀이

 일반적인 bfs로 풀이 하였다. 큐에 소요시간 정보와 현재 위치를 저장한 구조체를 넣어 문제를 해결했다.

하지만 여기서 다음 파이프의 조건을 판단할때 반대로 생각해야 한다는 것이 매우 중요했다. 이 문제의 핵심 포인트이다!! 

계속 지체되었던 부분인데 현재 위치에서 오른쪽으로 간다고 가정한다면, 다음위치의 파이프는 왼쪽이 뚫려있어야 한다! 


소스코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int n, m, r, c, l;
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};
int map[50][50];
bool visit[50][50];
struct node {
    int y, x, time;
    node(int _y, int _x, int _time) {
        y = _y;
        x = _x;
        time = _time;
    }
};
void init() {
    memset(map, 0, sizeof(map));
    memset(visit, 0, sizeof(visit));
 
    cin>>n>>m>>r>>c>>l;
    for (int y=0; y<n; y++) 
        for (int x=0; x<m; x++)
            cin>>map[y][x];
}
void bfs() {
    queue<node> q;
    q.push(node(r, c, 1));
    visit[r][c]=1;
    
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        int elapsedTime = q.front().time;
        int curPipeType = map[y][x];
        q.pop();
        
        if (elapsedTime == l) continue;
        
        for (int i=0; i<4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            int nextPipeType = map[ny][nx];
            
            if (ny<0 || nx<0 || ny>=n || nx>=m || nextPipeType == 0 || visit[ny][nx]) continue;
            /*******************************************************
                                 dx, dy 조건         
                    i=0 -> 상 / i=1 -> 하 / i=2 -> 좌 / i=3 -> 우
                    
                                 PipeType 조건
               1 -> 상/하/좌/우
               2 -> 상/하
               3 -> 좌/우
               4 -> 상/우
               5 -> 하/우
               6 -> 하/좌
               7 -> 상/좌
            *******************************************************/ 
            if (curPipeType == 2 && (i == 2 || i == 3)) continue;
            else if (curPipeType == 3 && (i == 0 || i == 1)) continue;
            else if (curPipeType == 4 && (i == 1 || i == 2)) continue;
            else if (curPipeType == 5 && (i == 0 || i == 2)) continue;
            else if (curPipeType == 6 && (i == 0 || i == 3)) continue;
            else if (curPipeType == 7 && (i == 1 || i == 3)) continue;
            
            // 여기서 반대가 되어야함
            // 즉 현재위치에서 왼쪽으로 간다면 다음 파이프는 오른쪽이 뚫려있어야 통과 가능 
            if (i == 0) {
                if (nextPipeType == 1 || nextPipeType == 2 || nextPipeType == 5 || nextPipeType == 6) {
                    visit[ny][nx]=1;
                    q.push(node(ny, nx, elapsedTime+1));
                }
            } else if (i == 1) {
                if (nextPipeType == 1 || nextPipeType == 2 || nextPipeType == 4 || nextPipeType == 7) {
                    visit[ny][nx]=1;
                    q.push(node(ny, nx, elapsedTime+1));
                }
            } else if (i == 2) {
                if (nextPipeType == 1 || nextPipeType == 3 || nextPipeType == 4 || nextPipeType == 5) {
                    visit[ny][nx]=1;
                    q.push(node(ny, nx, elapsedTime+1));
                }
            } else {
                if (nextPipeType == 1 || nextPipeType == 3 || nextPipeType == 6 || nextPipeType == 7) {
                    visit[ny][nx]=1;
                    q.push(node(ny, nx, elapsedTime+1));
                }
            }
        }
    }
}
int getAnswer() {
    int ans=0;
    for (int y=0; y<n; y++)
        for (int x=0; x<m; x++)
            if (visit[y][x]) ans++;
            
    return ans;    
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int tc;
    cin>>tc;
    for (int t=1; t<=tc; t++) {
        init();
        bfs();
        
        cout<<"#"<<t<<" "<<getAnswer()<<"\n";    
    }
    return 0;    
}
cs


반응형
저작자표시 (새창열림)

'Algorithm' 카테고리의 다른 글

[BOJ 15649] N과 M(1)  (0) 2019.10.30
[BOJ 13460] 구슬 탈출2  (0) 2019.10.09
[SWEA 5644] 무선충전  (0) 2019.08.19
[SWEA 1949] 등산로 조성  (0) 2019.08.19
[SWEA 1208] Flatten  (0) 2019.07.29
반응형

문제풀이

상당히 어렵게 푼 문제이다. 단순히 구현하는 문제(시뮬레이션)인데 공유하는 BC가 있을경우 선택을 잘 해야한다.

유저 a와 b의 경로를 2차원 배열에 저장하고 이동이 끝나면 시작위치의 좌표를 재조정한다.

이때 1) 유저 a만 충전하는 경우 2) 유저 b만 충전하는 경우 3) 유저 a,b 모두 충전하는 경우

총 3가지로 나누어 처리하였다.


소스코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef struct BC{
    int x, y, c, p;
}BC;
vector<BC> bc;
int ax, ay, bx, by;
int m, a, c, p;
int chargeA, chargeB;
// 정지, 상, 우, 하, 좌
int dx[]={0, 0, 1, 0, -1};
int dy[]={0, -1, 0, 1, 0};
int userPath[2][101];
 
int solve() {
    ax=ay=1;
    bx=by=10;
    chargeA=chargeB=0;
 
    for (int k=0; k<=m; k++) {
        vector<int> a,b;
        for (int i=0; i<bc.size(); i++) {
            if (abs(ax - bc[i].x) + abs(ay - bc[i].y) <= bc[i].c) 
                a.push_back(i);
            if (abs(bx - bc[i].x) + abs(by - bc[i].y) <= bc[i].c) 
                b.push_back(i);
        }
 
        int pA=0, pB=0, tmpSum=0;
        if (!a.empty() && b.empty()) {
            for (int i=0; i<a.size(); i++) {
                int tmpA = bc[a[i]].p;
                if (tmpSum < tmpA) {
                    tmpSum = tmpA;
                    pA = tmpA;
                }
            }
        }
        else if (a.empty() && !b.empty()) {
            for (int i=0; i<b.size(); i++) {
                int tmpB = bc[b[i]].p;
                if (tmpSum < tmpB) {
                    tmpSum = tmpB;
                    pB = tmpB;
                }
            }
        }
        else {
            for (int i=0; i<a.size(); i++) {
                for (int j=0; j<b.size(); j++) {
                    int tmpA = bc[a[i]].p;
                    int tmpB = bc[b[j]].p;
                    if (a[i] == b[j]) {
                        tmpA/=2;
                        tmpB/=2;
                    }
                    if (tmpSum < tmpA+tmpB) {
                        tmpSum = tmpA+tmpB;
                        pA = tmpA;
                        pB = tmpB;
                    }
                }
            }
        }
 
        ax += dx[userPath[0][k]];
        ay += dy[userPath[0][k]];
        bx += dx[userPath[1][k]];
        by += dy[userPath[1][k]];
        chargeA += pA;
        chargeB += pB;
    }
    return chargeA + chargeB;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int tc;
    cin>>tc;
    for (int t=1; t<=tc; t++) {
        cin>>m>>a;
        memset(userPath[0], 0, sizeof(userPath[0]));
        memset(userPath[1], 0, sizeof(userPath[1]));
        bc.clear();
 
        for (int i=0; i<m; i++) cin>>userPath[0][i];
        for (int i=0; i<m; i++) cin>>userPath[1][i];
 
        int y, x;
        for (int i=0; i<a; i++) {
            cin>>x>>y>>c>>p;
            bc.push_back(BC{x, y, c, p});
        }
 
        cout<<"#"<<t<<" "<<solve()<<"\n";
    }
    return 0;
}
cs


반응형
저작자표시 (새창열림)

'Algorithm' 카테고리의 다른 글

[BOJ 13460] 구슬 탈출2  (0) 2019.10.09
[SWEA 1953] 탈주범 검거  (0) 2019.08.23
[SWEA 1949] 등산로 조성  (0) 2019.08.19
[SWEA 1208] Flatten  (0) 2019.07.29
[SWEA 1219] 길찾기  (0) 2019.07.24
반응형

SSL 보안서버 인증서를 구매하여 사용하지 않고, Open SSL 인증서를 사용한 경우 git push시 SSL에러가 발생한다.


이를 해결하기 위해 CA에서 인증하는 절차를 무시하는 방법이 있다.

window 사용자는 cmd

mac 사용자는 terminal에서


1
git config --global http.sslVerify false
cs


명령어를 사용하여 global값을 설정한다.



반응형
저작자표시 (새창열림)

'CS 지식' 카테고리의 다른 글

[운영체제] 프로세스와 쓰레드  (0) 2019.02.21
[CS기초지식] REST API의 특징  (0) 2018.12.13
[C/S 기초] 미들웨어와 웹 서버(Middle Ware and Web Server)  (0) 2018.11.26
[RESTful이란?] RESTful? 간략히 알아보기  (2) 2018.09.20
객체 지향의 4대 특성  (0) 2018.09.03

+ Recent posts

티스토리툴바