'알고리즘 문제풀이/백준' 카테고리의 글 목록 (4 Page)

알고리즘 문제풀이/백준

[C++] 백준 8981 - 입력숫자

2020. 4. 30. 12:42

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

8981번: 입력숫자

첫 줄에는 정수 N이 제시되어 있고, 그 다음 줄에는 N개의 양의 정수가 빈칸을 사이에 두고 기록되어 있어야 한다. 만일 입력을 생성하는 mystery.c의 입력파일 X가 없는 경우에는 음수인 -1 을 첫 줄에 출력하면 된다.

www.acmicpc.net

<풀이>

1. 주어진 코드가 어떻게 동작하는지 이해하고, 코드를 구현한다.

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

#include <iostream>
#include <cstring>
using namespace std;
 
int N;
int X[101];
 
int main() {
 
    cin >> N;
 
    //초기화
    memset(X, 0, sizeof(X));
    int value = 0, from = 0;
 
    //구현
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
 
        from = (from + value) % N;
        value = X[from];
        while (value > 0) {
            from = (from + 1) % N;
            value = X[from];
        }
 
        X[from] = num;
        value = num;
    }
 
    cout << N << "\n";
    for (int i = 0; i < N; i++) {
        cout << X[i] << " ";
    }
}

구현에 대해 알아볼 수 있는 문제였습니다.

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[Python] 백준 10834 - 벨트 (0)	2020.06.21
[Python] 백준 10833 - 사과 (0)	2020.06.21
[C++] 백준 8980 - 택배 (0)	2020.04.30
[C++] 백준 2512 - 예산 (0)	2020.04.30
[C++] 백준 8979 - 올림픽 (0)	2020.04.30

[C++] 백준 8980 - 택배

2020. 4. 30. 12:40

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

8980번: 택배

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호

www.acmicpc.net

<풀이>

1. 입력값으로 주어지는 택배 정보들을 정렬하여, 보낼 수 있는 최대 택배 갯수를 출력합니다.

<해법>

1. 택배 정보들을 정렬하는 방법.

=> 정렬하는 방법으로 가장 먼저, 보내는 마을 번호 순으로 정렬을 생각할 수 있습니다. 하지만 이렇게 정렬할 경우, 중간지점에서 많은 택배를 배송할 수 있음에도 이미 가지고 있는 택배 때문에 많은 택배를 배송하지 못하는 경우가 생깁니다. 아래 그림과 같은 경우가 그 예 입니다.

1번 마을에서 50개를 담지않고 2,3,4번 마을 박스를 담았다면 150개를 배송할 수 있습니다.

따라서, 정렬은 받는 마을 순으로 해야합니다.

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

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
 
struct box {
    int str;
    int fin;
    int boxCnt;
};
 
int N, C, M;
vector<box> v;
int town[2001];
int res = 0;
 
bool cmp(const box& lhs, const box& rhs) {
    if (lhs.fin == rhs.fin) {
        return lhs.str < rhs.str;
    }
    return lhs.fin < rhs.fin;
}
 
int main() {
 
    //입력
    cin >> N >> C >> M;
    for (int i = 0; i < M; i++) {
        int str, fin, boxCnt;
        cin >> str >> fin >> boxCnt;
        v.push_back({ str,fin,boxCnt });
    }
 
    //마을마다 트럭에 담긴 박스 갯수(0으로 초기화)
    memset(town, 0, sizeof(town));
 
    //배열 정렬 -> 도착지점이 작은 순으로 정렬
    sort(v.begin(), v.end(), cmp);
 
    for (int i = 0; i < M; i++) {
 
        int str = v[i].str;
        int fin = v[i].fin;
        int ableBox = v[i].boxCnt;
 
        //지나가는 마을마다 트럭 자리 확인
        for (int j = str; j < fin; j++) {
            //트럭안에 남은 자리 > 보내려는 박스 -> 박스를 모두 보낼 수 있음
            if (C - town[j] > ableBox) {
 
            }
            //트럭안에 남은 자리 <= 보내려는 박스 -> 남은 자리만 박스를 보낼 수 있음
            else {
                ableBox = C - town[j];
            }
        }
 
        //지나가는 마을의 트럭 자리 채우기
        for (int j = str; j < fin; j++) {
            town[j] += ableBox;
        }
 
        res += ableBox;
    }
 
    //출력
    cout << res;
}
 

구현에 대해 알아볼 수 있는 문제였습니다.

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[Python] 백준 10833 - 사과 (0)	2020.06.21
[C++] 백준 8981 - 입력숫자 (0)	2020.04.30
[C++] 백준 2512 - 예산 (0)	2020.04.30
[C++] 백준 8979 - 올림픽 (0)	2020.04.30
[C++] 백준 1726 - 로봇 (0)	2020.04.30

[C++] 백준 2512 - 예산

2020. 4. 30. 12:37

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

2512번: 예산

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.

www.acmicpc.net

<풀이>

1. 주어진 입력 값들로 모든 예산 요청이 배정될 수 있는지 없는지를 판단하여 결과를 출력한다.

<해법>

1. 모든 예산 요청이 배정될 수 없는경우 -> 상한액 설정하는 방법.

=> 모든 상한액들을 탐색해 보아야 합니다. 이 때 상한액의 범위를 생각해 보아야 합니다. 상한액의 범위는 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
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

#include <iostream>
using namespace std;
 
int main() {
 
    int N;
    int arr[10000];
    long long M;
 
    //처음 요청 금액의 합
    long long first_req_sum = 0;
    //요청 금액 중 가장 큰 금액
    int biggest = 0;
    long long res = 0;
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        first_req_sum += arr[i];
        if (arr[i] > biggest) {
            biggest = arr[i];
        }
    }
    cin >> M;
 
    //모든 요청이 배정될 수 있는 경우 -> 1번 조건
    if (first_req_sum <= M) {
        res = biggest;
    }
    //모든 요청이 배정될 수 없는 경우 -> 2번 조건 -> 상한액 찾기
    else {
        //상한액 : 0 ~ biggest
        int str = 0;
        int fin = biggest;
 
        //이분 탐색
        while (str <= fin) {
 
            int mid = (str + fin) / 2;
 
            long long tmpSum = 0;
            for (int i = 0; i < N; i++) {
                if (arr[i] < mid) {
                    tmpSum += arr[i];
                }
                else {
                    tmpSum += mid;
                }
            }
 
            if (tmpSum > M) {
                fin = mid - 1;
            }
            else if (tmpSum < M) {
                str = mid + 1;
                res = mid;
            }
            //모든 예산을 다 사용할 수 있는 경우
            else {
                res = mid;
                break;
            }
        }
    }
 
    //출력
    cout << res;
 
    return 0;
}
 

이분탐색에 대해 알아볼 수 있는 문제였습니다.

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 8981 - 입력숫자 (0)	2020.04.30
[C++] 백준 8980 - 택배 (0)	2020.04.30
[C++] 백준 8979 - 올림픽 (0)	2020.04.30
[C++] 백준 1726 - 로봇 (0)	2020.04.30
[C++] 백준 2513 - 통학버스 (0)	2020.04.30

[C++] 백준 8979 - 올림픽

2020. 4. 30. 12:34

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

8979번: 올림픽

입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 �

www.acmicpc.net

<풀이>

1. 국가 번호를 index로 해서 금메달, 은메달, 동메달 배열을 따로 생성하여 입력받는다.

2. 1번 국가부터 입력받는 N번 국가까지 K번 국가보다 잘한 국가 수를 찾는다.

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>
using namespace std;
 
int N, K;
int gold[1001];
int silver[1001];
int bronze[1001];
int res = 0;
 
int main() {
 
    //입력
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        int index;
        cin >> index;
        cin >> gold[index] >> silver[index] >> bronze[index];
    }
 
    //1번 국가부터 N번 국가까지 K번 국가보다 더 잘한 국가일 경우 res++
    for (int i = 1; i <= N; i++) {
        if (gold[i] > gold[K]) {
            res++;
        }
        else if (gold[i] == gold[K]) {
            if (silver[i] > silver[K]) {
                res++;
            }
            else if (silver[i] == silver[K]) {
                if (bronze[i] > bronze[K]) {
                    res++;
                }
            }
        }
    }
 
    //출력
    cout << res + 1;
}
 

구현에 대해 알아볼 수 있는 문제였습니다.

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 8980 - 택배 (0)	2020.04.30
[C++] 백준 2512 - 예산 (0)	2020.04.30
[C++] 백준 1726 - 로봇 (0)	2020.04.30
[C++] 백준 2513 - 통학버스 (0)	2020.04.30
[C++] 백준 2511 - 카드놀이 (0)	2020.04.30

[C++] 백준 1726 - 로봇

2020. 4. 30. 12:31

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

1726번: 로봇

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다. 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다. 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다. 공장 내 궤도가 설치되

www.acmicpc.net

<풀이>

1. 로봇 시작위치부터 도착위치까지 움직일 수 있는 5가지 경우(1,2,3칸 가기, 방향 왼쪽,오른쪽 전환)를 모두 탐색한다.

2. 로봇이 도착위치에 도착하면 내린 명령의 최소 개수를 구한다.

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
113
114
115
116
117
118
119
120
121
122
123
124
125

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
struct pos {
    int x, y;
};
 
struct robot {
    pos p;
    int dir;
    int cnt;
};
 
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int M, N;
int map[100][100];
bool visited[100][100][4];
vector<robot> v;
int res;
 
bool inner(int x, int y) {
    if (x < 0 || y < 0 || x >= M || y >= N) {
        return false;
    }
    return true;
}
 
void bfs(robot str) {
    queue<robot> q;
    q.push(str);
    visited[str.p.x][str.p.y][str.dir] = true;
 
    while (!q.empty()) {
        robot cur = q.front();
        q.pop();
 
        //목적지 도달 - 종료
        if (cur.p.x == v[1].p.x && cur.p.y == v[1].p.y && cur.dir == v[1].dir) {
            res = cur.cnt;
            return;
        }
 
        //명령 Go
        for (int i = 1; i <= 3; i++) {
            robot nxt = cur;
            nxt.p.x += di[nxt.dir] * i;
            nxt.p.y += dj[nxt.dir] * i;
            
            //한칸,두칸,세칸 가면서 범위를 넘어가거나 벽을 만날 경우, 다음 칸은 할 필요X 
            if (!inner(nxt.p.x, nxt.p.y)) {
                break;
            }
            if (map[nxt.p.x][nxt.p.y] == 1) {
                break;
            }
 
            if (map[nxt.p.x][nxt.p.y] == 0 && !visited[nxt.p.x][nxt.p.y][nxt.dir]) {
                nxt.cnt++;
                q.push(nxt);
                visited[nxt.p.x][nxt.p.y][nxt.dir] = true;
            }
        }
        
        //명령 Turn dir
        for (int i = 0; i < 4; i++) {
            robot nxt = cur;
 
            //2로 나눈 나머지가 다른 방향만 탐색(왼쪽, 오른쪽)
            if (i % 2 != nxt.dir % 2) {
                nxt.dir = i;
                if (!visited[nxt.p.x][nxt.p.y][nxt.dir]) {
                    nxt.cnt++;
                    q.push(nxt);
                    visited[nxt.p.x][nxt.p.y][nxt.dir] = true;
                }
            }
        }
    }
}
 
int main() {
 
    //입력
    cin >> M >> N;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
    for (int i = 0; i < 2; i++) {
        int x, y, dir;
        cin >> x >> y >> dir;
        robot tmp = { x,y,dir,0 };
        v.push_back(tmp);
    }
 
    //입력값 조정
    //좌표 - 1(배열과 맞추기 위해), 방향 북동남서(왼쪽 오른쪽 쉽게 하기 위해)
    for (int i = 0; i < 2; i++) {
        v[i].p.x -= 1;
        v[i].p.y -= 1;
        if (v[i].dir == 1) {
            v[i].dir = 1;
        }
        else if (v[i].dir == 2) {
            v[i].dir = 3;
        }
        else if (v[i].dir == 3) {
            v[i].dir = 2;
        }
        else {
            v[i].dir = 0;
        }
    }
 
    //로봇 처음 위치에서 탐색 시작
    bfs(v[0]);
 
    //출력
    cout << res;
}
 

BFS에 대해 알아볼 수 있는 문제였습니다.

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 2512 - 예산 (0)	2020.04.30
[C++] 백준 8979 - 올림픽 (0)	2020.04.30
[C++] 백준 2513 - 통학버스 (0)	2020.04.30
[C++] 백준 2511 - 카드놀이 (0)	2020.04.30
[C++] 백준 6087 - 레이저 통신 (0)	2020.04.30

[C++] 백준 2513 - 통학버스

2020. 4. 30. 12:26

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

2513번: 통학버스

첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2<=N<=30,000이다. 두 번째 정수 K는 1<=K<=2,000이며, 통학버스의 정원이다. 세 번째 정수 S는 학교의 위치를 나타낸다. 둘째 줄부터 N+1번째 줄에는 각 아파트 단지의 위치를 나타내는 정수와 이 단지에 사는 학생 수를 나타내는 정수가 빈칸을 사이에 두고 주어진다. 학교와 아파트 단지의 좌표는 0 이상 100

www.acmicpc.net

<풀이>

1. 학생이 사는 아파트의 범위를 저장한다.(학생이 사는 아파트 중 가장 작은 index, 가장 큰 index를 저장한다.)

2. 아파트 중 가장 작은 index에서 시작해서 학교까지 버스에 태울 수 있을 만큼 모두 태운다.

3. 학교보다 왼쪽에 있는 학생들을 모두 태울 때 까지 반복하고, 거리를 저장한다.

4. 학교보다 오른쪽에 사는 학생도 2,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

#include <iostream>
using namespace std;
 
int N, K, S;
int arr[100000];
int aptStr = -1, aptEnd = 0;
int res = 0;
 
int main() {
 
    //입력
    cin >> N >> K >> S;
    for (int i = 0; i < N; i++) {
        int index, num;
        cin >> index >> num;
        arr[index] = num;
 
        //학생이 사는 아파트 중 처음과 끝 아파트 찾기 
        if (aptStr == -1 || index < aptStr) {
            aptStr = index;
        }
        if (index > aptEnd) {
            aptEnd = index;
        }
    }
 
    //처음 아파트 부터 학교까지 버스 이동거리 구하기
    while (aptStr < S) {
        //str : 학생을 태우기 시작한 아파트, end : 여기 학생까지 태운 아파트, tmpK : 버스에 남은 자리
        int str = aptStr, end = aptStr, tmpK = K;
 
        if (arr[str] > 0) {
            while (true) {            
                if (tmpK == 0 || end == S) {
                    aptStr = end;
                    res += (S - str) * 2;
                    break;
                }
 
                if (arr[end] > tmpK) {
                    arr[end] -= tmpK;
                    tmpK = 0;
                }
                else {
                    tmpK -= arr[end];
                    arr[end] = 0;
                    end++;
                }
                
            }
        }
        else {
            aptStr++;
        }
    }
 
    //끝 아파트 부터 학교까지 버스 이동거리 구하기
    while (aptEnd > S) {
        int str = aptEnd, end = aptEnd, tmpK = K;
 
        if (arr[str] > 0) {
            while (true) {
                if (tmpK == 0 || end == S) {
                    aptStr = end;
                    res += (str - S) * 2;
                    break;
                }
                if (arr[end] > tmpK) {
                    arr[end] -= tmpK;
                    tmpK = 0;
                }
                else {
                    tmpK -= arr[end];
                    arr[end] = 0;
                    end--;
                }
            }
        }
        else {
            aptEnd--;
        }
    }
    cout << res;
 
    //예제 테스트 케이스
    /*7 4 4
        0 5
        1 2
        2 3
        6 4
        7 6
        8 6
        9 7*/
    //output : 66
}
 

구현에 대해 알아볼 수 있는 문제였습니다.

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 8979 - 올림픽 (0)	2020.04.30
[C++] 백준 1726 - 로봇 (0)	2020.04.30
[C++] 백준 2511 - 카드놀이 (0)	2020.04.30
[C++] 백준 6087 - 레이저 통신 (0)	2020.04.30
[C++] 백준 1938 - 통나무 옮기기 (0)	2020.04.30

[C++] 백준 2511 - 카드놀이

2020. 4. 30. 12:21

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

2511번: 카드놀이

첫 번째 줄에는 게임이 끝난 후, A와 B가 받은 총 승점을 순서대로 빈칸을 사이에 두고 출력한다. 두 번째 줄에는 이긴 사람이 A인지 B인지 결정해서, 이긴 사람을 문자 A 또는 B로 출력한다. 만약 �

www.acmicpc.net

<풀이>

1. A, B의 점수를 입력받는다.

2. 입력받은 점수들로 계산한다. 각각 점수계산, 마지막 승자를 변수에 저장한다.

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

#include <iostream>
using namespace std;
 
int A[10];
int B[10];
int scoreA = 0;
int scoreB = 0;
char lastWin = 'D';
 
int main() {
 
    //입력
    for (int i = 0; i < 10; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < 10; i++) {
        cin >> B[i];
    }
 
    //점수계산
    for (int i = 0; i < 10; i++) {
        if (A[i] > B[i]) {
            scoreA += 3;
            lastWin = 'A';
        }
        else if (A[i] < B[i]) {
            scoreB += 3;
            lastWin = 'B';
        }
        else {
            scoreA++;
            scoreB++;
        }
    }
 
    //출력
    cout << scoreA << " " << scoreB << "\n";
 
    if (scoreA > scoreB) {
        cout << 'A';
    }
    else if (scoreA < scoreB) {
        cout << 'B';
    }
    else {
        cout << lastWin;
    }
 
    return 0;
}
 

구현에 대해 알아볼 수 있는 문제였습니다.

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 1726 - 로봇 (0)	2020.04.30
[C++] 백준 2513 - 통학버스 (0)	2020.04.30
[C++] 백준 6087 - 레이저 통신 (0)	2020.04.30
[C++] 백준 1938 - 통나무 옮기기 (0)	2020.04.30
[C++] 백준 2174 - 로봇 시뮬레이션 (0)	2020.04.30

[C++] 백준 6087 - 레이저 통신

2020. 4. 30. 12:19

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

6087번: 레이저 통신

문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.

www.acmicpc.net

<풀이>

1. 출발 'C' 지점에서 레이저를 발사하여, 각 지점마다 필요한 거울 개수를 세준다.

2. 도착 'C' 지점에 도착하면 사용한 거울 개수를 출력한다.

<해법>

1. 필요한 거울 개수를 세는 방법.

=> 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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
struct pos {
    //좌표
    int x, y;
};
 
struct laser {
    //좌표
    pos l;
    //거울 개수
    int cnt;
};
 
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int W, H;
char map[100][100];
bool visited[100][100];
vector<pos> cPos;
int res;
 
void bfs(laser st) {
    queue<laser> q;
    q.push(st);
    visited[st.l.x][st.l.y] = true;
 
    while (!q.empty()) {
        laser cur = q.front();
        q.pop();
 
        //도착지점에 도착 - 종료
        if (cur.l.x == cPos[1].x && cur.l.y == cPos[1].y) {
            res = cur.cnt;
            return;
        }
 
        //4방향 탐색
        for (int i = 0; i < 4; i++) {
            laser nxt = cur;
 
            //방향으로 갈 수 있는곳 까지 레이저 발사
            while (true) {
                nxt.l.x += di[i];
                nxt.l.y += dj[i];
 
                //레이저가 범위를 넘어섰을 경우, 레이저가 벽을 만났을 경우 - 반복문 탈출
                if (nxt.l.x < 0 || nxt.l.y < 0 || nxt.l.x >= H || nxt.l.y >= W) {
                    break;
                }
                if (map[nxt.l.x][nxt.l.y] == '*') {
                    break;
                }
 
                //이전에 방문하지 않았던 경우 - 거울 개수 + 1
                if (!visited[nxt.l.x][nxt.l.y]) {
                    nxt.cnt = cur.cnt + 1;
                    visited[nxt.l.x][nxt.l.y] = true;
                    q.push(nxt);
                }
            }
        }
    }
}
 
int main() {
 
    //입력
    cin >> W >> H;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> map[i][j];
 
            //출발지점, 도착지점 찾기
            if (map[i][j] == 'C') {
                cPos.push_back({ i,j });
            }
        }
    }
 
    //출발지점
    laser st = { {cPos[0].x, cPos[0].y}, -1 };
 
    //출발지점부터 탐색
    bfs(st);
 
    //출력
    cout << res;
 
    return 0;
}
 

BFS와 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 2513 - 통학버스 (0)	2020.04.30
[C++] 백준 2511 - 카드놀이 (0)	2020.04.30
[C++] 백준 1938 - 통나무 옮기기 (0)	2020.04.30
[C++] 백준 2174 - 로봇 시뮬레이션 (0)	2020.04.30
[C++] 백준 3987 - 보이저 1호 (0)	2020.04.30

PREV 1 2 3 4 5 6 NEXT

알고리즘 고수가 되기까지