BOJ : https://www.acmicpc.net/problem/5014

github : https://github.com/junho0956/Algorithm/blob/master/5014/5014/%EC%86%8C%EC%8A%A4.cpp

 

간단한 BFS 문제입니다.

주의해야할 점이 있다면 건물은 1층부터 F 층까지 있다는 점으로

범위가 벗어나면 갈 수 없다는 점입니다

 

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
#include <iostream>
#include <queue>
using namespace std;
 
queue<pair<int, int> > q;
bool visit[1000001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    bool check = false;
    int f, s, g, u, d;
    cin >> f >> s >> g >> u >> d;
 
    q.push({ s,0 });
    while (!q.empty()) {
        int now = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (now > f) continue;
        if (now < 1) continue;
        if (visit[now]) continue;
        visit[now] = true;
 
        if (now == g) {
            cout << cnt;
            check = true;
            break;
        }
 
        if (u)q.push({ now + u, cnt + 1 });
        if (d)q.push({ now - d, cnt + 1 });
    }
 
    if (!check) cout << "use the stairs";
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2661번 좋은수열  (0) 2020.01.31
BOJ 1759번 암호 만들기  (0) 2020.01.31
BOJ 3108번 로고  (0) 2020.01.31
BOJ 2186번 문자판  (0) 2020.01.27
BOJ 2251번 물통  (0) 2020.01.24

BOJ : https://www.acmicpc.net/problem/3108

github : https://github.com/junho0956/Algorithm/blob/master/3108/3108/%EC%86%8C%EC%8A%A4.cpp

 

이 문제를 푸는 요령은 2가지가 있습니다.

 

1) BFS 또는 DFS 를 이용해서 한붓그리기를 코드

2) 애초에 사각형이 겹치는 부분에 대한 탐색을 하면되니 DFS 를 이용한 사각형의 겹침 부분을 코드

 

1번으로 풀다가 틀려서 2번으로 방법을 변경하였습니다.

check_box() 에 대해서 설명해보자면

check_box() 는 사각형이 겹치는지 안겹치는지 판단하는 함수로,

false 를 반환할 때 겹친다라고 가정하였습니다.

 

lx[a] < fx[b] || ly[a] < fy[b] 의 부분은 두 사각형이 아예 떨어져있는 경우로

true 를 반환하게 되어, 사각형이 겹치지 않는다를 의미하게 됩니다.

fx[a] > fx[b] && lx[a] < lx[b] && fy[a] > fy[b] && ly[a] < ly[b] 의 부분은

한 사각형이 다른 사각형을 포함하고 있음을 나타내는 경우로

true 를 반환하게 되어, 사각형이 겹치지 않는다를 의미하게 됩니다.

 

둘다 만족하지 않아 false 를 반환하게 되는 경우는 무조건 사각형이 겹치게 됨을 의미하게 되어,

다른 사각형을 확인하게 되는 dfs() 로 진입하게 됩니다.

 

문제의 중요한 부분은 (0,0) 부터 탐색을 시작해야한다는 것이고,

이를 위해서 반복문을 0<=N 으로 작성하였습니다.

일부러 cin >> +1 해가면서 좌표를 받은 이유도 첫 좌표는 (0,0),(0,0) 이라는 점(사각형이 됩니다)을 사용하기

위해서 입니다.

 

마지막에 ans-1 의 -1 을 해준 이유 역시 반복문은 최소 1번이상 실행되게 되어있는데

(0,0) 에 걸치는 사각형이 존재할 수 있기 때문입니다.

 

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
#include <iostream>
using namespace std;
#pragma warning(disable:4996)
 
int N;
int fy[1001], fx[1001], lx[1001], ly[1001];
bool visit[1001];
 
bool check_box(int a, int b) {
    return (lx[a] < fx[b] || ly[a] < fy[b] || fx[a] > fx[b] && lx[a] < lx[b] && fy[a] > fy[b] && ly[a] < ly[b]);
}
 
void dfs(int now) {
 
    visit[now] = true;
    for (int i = 0; i <= N; i++) {
        if (visit[i]) continue;
        if (!check_box(now,i) && !check_box(i,now)) {
            dfs(i);
        }
    }
 
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    bool temp = false;
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> fx[i+1] >> fy[i+1] >> lx[i+1] >> ly[i+1];
    }
 
    int ans = 0;
    
    for (int i = 0; i <= N; i++) {
        if (visit[i]) continue;
        ans++;
        dfs(i);
    }
 
    cout << ans - 1;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1759번 암호 만들기  (0) 2020.01.31
BOJ 5014번 스타트링크  (0) 2020.01.31
BOJ 2186번 문자판  (0) 2020.01.27
BOJ 2251번 물통  (0) 2020.01.24
BOJ 1525번 퍼즐  (0) 2020.01.24

BOJ : https://www.acmicpc.net/problem/2186

github : https://github.com/junho0956/Algorithm/blob/master/2186/2186/%EC%86%8C%EC%8A%A4.cpp

 

처음에는 BFS, DFS 로 둘다 탐색해보았는데

전부다 시간초과가 되서 멘탈이 나갔던 문제였다. 마침 설날이라 놀고싶기도 했고,, ??

 

처음에 bfs 에 의해 시간초과가 발생해서

시도해본게 dfs 로 첫 발생지점에 대한 dp 였다.

2중포문을 돌면서 첫 알파벳을 찾는 순간 dp를 초기화하고

이 부분에 대한 dfs 를 돌면서 탐색하지 않아도 되는 부분은 줄여나가는 식으로 했었다.

역시 시간초과였다.

 

그래서 다른방법을 생각해보았다.

통째로 dp를 적용할 수 있을까?

그래서 생각한게 3차원 배열의 dp였다

원래 dfs 를 적용했을때는 100*100 dp 를 사용했는데

3차원 배열을 사용하면 인덱스별로 dp 를 적용할 수 있을 것 같았다.

그래서 사용한 배열이 100*100*80 dp 이고

 

** 현재 탐색하고있는 알파벳 부분의 인덱스를 알고 있을 때 dp 값이 존재하지 않는다면 탐색,

** 존재한다면 리턴 하는 식으로 구현해보았다.

 

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
// bfs 로 풀어보니 시간초과가 발생한다
// dfs 로 풀게되면 시간초과가 발생하긴 하는데, dp 같은 느낌의 방법을
// 적용해볼 수 있을 것 같다.
 
#include <iostream>
#include <string>
using namespace std;
 
// 최대길이가 80 이라고했으니 80에 대한 dp 배열을 잡는다.
// 80 의 의미는 임의의 (y,x) 에 도착했을 때
// 현재 문자열의 인덱스 중 몆번째 인덱스를 탐색하는지 알고있다면,
// 이때 dp 배열이 초기화상태가 아니라면 이미 이 부분은 탐색된 것이니
// 탐색을 중단하고 값을 가져간다는 느낌으로 간다.
int dp[100][100][80];
char arr[100][100];
int mx[4] = { -1,1,0,0 };
int my[4] = { 0,0,1,-1 };
int N, M, K;
string ans;
 
int solve(string str, int y, int x, int idx) {
 
    if (dp[y][x][idx] != -1) return dp[y][x][idx];
 
    if (str.size() >= ans.size()) return 1;
    dp[y][x][idx] = 0;
    for (int i = 0; i < 4; i++) {
        int yy = y, xx = x;
        for (int j = 1; j <= K; j++) {
            yy += my[i];
            xx += mx[i];
            if (yy >= 0 && xx >= 0 && yy < N && xx < M && arr[yy][xx] == ans[idx+1]) {
                dp[y][x][idx] += solve(str + ans[idx+1], yy, xx, idx + 1);
            }
        }
    }
 
    return dp[y][x][idx];
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> arr[i][j];
 
    cin >> ans;
 
    int total = 0;
    string f;
    f.push_back(ans[0]);
 
    // 밑부분에서 solve(f,i,j,0) 을 할때 dp return 을 하지 않기 때문에
    // 일부러 -1 로 초기화 해주었다.
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) for (int k = 0; k < 80; k++) dp[i][j][k] = -1;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == ans[0]) {
                total += solve(f, i, j, 0);
            }
        }
    }
 
    cout << total;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 5014번 스타트링크  (0) 2020.01.31
BOJ 3108번 로고  (0) 2020.01.31
BOJ 2251번 물통  (0) 2020.01.24
BOJ 1525번 퍼즐  (0) 2020.01.24
BOJ 9019번 DSLR  (0) 2020.01.23

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

github : https://github.com/junho0956/Algorithm/blob/master/2251/2251/%EC%86%8C%EC%8A%A4.cpp

 

문제에서 요구하는대로 구현하기는 했는데 썩 깔끔하지는 않다.

그 이유는 .. 아직 set 사용법에 대한 정확한 사용법을 몰라서

 

처음에는 typedef 로 선언해둔 구조체형인 pii 를 이용해서

set<pii> 형식으로 사용하였는데

다 코드한 후에 실행해보니, typedef 템플릿에 대한 어떤 컴파일 오류가 발생하였다.

오류를 이해하기 힘들어 이번에는 아래의 piiset 과 같은 선언을 이용해보았는데

다행히 컴파일오류가 나지 않아 AC 를 받게 되었다.

 

핵심은 문제가 요구하는 그대로 따라가주면 된다.

한 컵을 다 채우거나 자신의 컵이 비워질떄까지 채우기 위한 조건 그대로 코드해주면 된다.

 

맨 아래의 erase ( unique ~ ) 는 중복을 제거하는 방법으로,

 

간단히 설명하면

erase 가 컨테이너의 값을 지우는 함수이고

unique 는 컨테이너 내부의 값들 중 중복의 값이 없게 나열하는 함수이다.

unique 가 종료되고 나면 중복 정리가 끝난 뒷부분에 이터레이터가 반환되고,

이 부분부터 end 까지 erase 가 실행되어 중복제거가 완료된다.

 

set 을 쓰고나니 코드하는 부분이 더욱 편해진 것은 사실인 것 같다.

좀더 자주 사용해보도록 해야겠다.

 

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
#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
typedef struct pii {
    int a, b, c;
};
typedef pair<int, pair<int, int> > piiset;
 
vector<int> v;
queue<pii> q;
set<piiset> visit;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int A, B, C;
    cin >> A >> B >> C;
 
    q.push({ 0, 0, C });
 
    while (!q.empty()) {
        pii value = q.front();
        piiset valueset;
        valueset.first = value.a;
        valueset.second.first = value.b;
        valueset.second.second = value.c;
        q.pop();
 
        if (visit.find(valueset) != visit.end()) continue;
        visit.insert(valueset);
 
        if (value.a == 0) v.push_back(value.c);
        else {
            if (value.a <= B - value.b) q.push({ 0,value.b + value.a,value.c });
            else q.push({ value.a - (B - value.b), B, value.c });
            if (value.a <= C - value.c) q.push({ 0,value.b,value.c + value.a });
            else q.push({ value.a - (C - value.c), value.b, C });
        }
 
        if (value.b <= A - value.a) q.push({ value.a + value.b, 0, value.c });
        else q.push({ A, value.b - (A - value.a), value.c });
        if (value.b <= C - value.c) q.push({ value.a, 0, value.c + value.b });
        else q.push({ value.a, value.b - (C - value.c), C });
 
        if (value.c <= A - value.a) q.push({ value.a + value.c, value.b, 0 });
        else q.push({ A, value.b, value.c - (A-value.a) });
        if (value.c <= B - value.b) q.push({ value.a, value.b + value.c, 0 });
        else q.push({ value.a, B, value.c - (B - value.b) });
    }
 
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
 
    for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 3108번 로고  (0) 2020.01.31
BOJ 2186번 문자판  (0) 2020.01.27
BOJ 1525번 퍼즐  (0) 2020.01.24
BOJ 9019번 DSLR  (0) 2020.01.23
BOJ 1963번 소수 경로  (0) 2020.01.23

+ Recent posts

티스토리툴바