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

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

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

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

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

 

1938번: 통나무 옮기기

첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4<=N<=50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사이에는 빈칸이 없다. 통나무와 최종 위치의 개수는 1개이다.

www.acmicpc.net

<풀이>

1. 초기 통나무 상태를 구하고, bfs를 시작한다.

2. 조건에 맞춰서 통나무를 움직이고, 도착지점에 도달하면 함수를 종료한다.

3. 움직인 횟수를 출력한다.

​

<해법>

1. BFS

=> 문제에서 BFS를 이용해야겠다는 것은 알 수 있습니다. 이제 중요한 것은 큐에 담을 자료형과 방문 처리 입니다.

결국, 어떻게 큐에 담아서( = 큐에 담을 자료형) 그 중 의미있는 정보만을 골라서( = 방문하지 않은 정보를 고름) 다시 큐에 담아 탐색을 진행하는 방법을 생각해야 합니다.

​

- 큐에 담을 자료형

bfs를 동작할 때 필요한 정보들을 담았습니다.

위 문제에서는 가장먼저 통나무 세 개의 좌표들이 필요합니다. 또한 회전을 해야하므로 눕혀있는 상태, 출력할 값인 움직인 횟수가 필요합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//좌표
struct pos {
    int x, y;
};
 
//움직일 통나무 3개
struct logs {
 
    //각각 통나무 좌표
    pos A, B, C;
 
    //통나무가 눕혀있는 상태
    int floating;
 
    //움직인 횟수
    int moveCnt;
};

- 방문 처리

완전 탐색인 bfs를 효율적으로 사용하기 위해서는 필요없는 탐색을 줄이는 것이 중요합니다.

필요없는 탐색이란 탐색할 범위를 넘어섰거나, 이전에 탐색했던 것을 탐색하는 것입니다.

그 중 두번째 비효율 탐색을 줄이는 방법으로, 방문 처리가 있습니다.

위 문제를 예로 들겠습니다.

만약 문제에서 방문처리를 3개 통나무의 좌표로 하게 된다면, 아래와 같은 비효율 탐색이 발생한다.

따라서, 방문처리는 가운데 통나무(B통나무)의 좌표와 눕혀있는 상태로 정해야한다.

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
//좌표
struct pos {
    int x, y;
};
 
//움직일 통나무 3개
struct logs {
 
    //각각 통나무 좌표
    pos A, B, C;
 
    //통나무가 눕혀있는 상태
    int floating;
 
    //움직인 횟수
    int moveCnt;
};
 
//앞 4개 : 상하좌우, 뒤 4개 : 대각방향
int di[] = { -1,0,1,0,-1,1,1,-1 };
int dj[] = { 0,1,0,-1,1,1,-1,-1 };
 
int N;
char map[52][52];
 
//visited[가운데 통나무 행][가운데 통나무 열][눕혀있는 상태]
bool visited[52][52][2];
 
queue<logs> q;
int res = 0;
 
bool inner(int ai, int aj, int bi, int bj, int ci, int cj) {
    if (ai <= 0 || aj <= 0 || bi <= 0 || bj <= 0 || ci <= 0 || cj <= 0 || ai > N || aj > N || bi > N || bj > N || ci > N || cj > N) {
        return false;
    }
    return true;
}
 
void bfs() {
    while (!q.empty()) {
        logs cur = q.front();
        q.pop();
 
        //3개 모두 옮겼을 시 - 종료
        if (map[cur.A.x][cur.A.y] == 'E' && map[cur.B.x][cur.B.y] == 'E' && map[cur.C.x][cur.C.y] == 'E') {
            res = cur.moveCnt;
            return;
        }
 
        //상,하,좌,우로 움직일 수 있는지 판단 후 큐에 담기
        for (int i = 0; i < 4; i++) {
            logs nxt = cur;
            nxt.A.x += di[i];
            nxt.A.y += dj[i];
            nxt.B.x += di[i];
            nxt.B.y += dj[i];
            nxt.C.x += di[i];
            nxt.C.y += dj[i];
 
            //옮긴 3개 통나무의 좌표가 범위 안에 있는지 판단
            if (!inner(nxt.A.x, nxt.A.y, nxt.B.x, nxt.B.y, nxt.C.x, nxt.C.y)) {
                continue;
            }
 
            //옮긴 3개 통나무 좌표에 다른 나무가 있거나, 이전에 같은 모양으로 방문한적이 있는지 판단
            if (map[nxt.A.x][nxt.A.y] == '1' || map[nxt.B.x][nxt.B.y] == '1' || map[nxt.C.x][nxt.C.y] == '1' || visited[nxt.B.x][nxt.B.y][nxt.floating]) {
                continue;
            }
 
            nxt.moveCnt++;
            visited[nxt.B.x][nxt.B.y][nxt.floating] = true;
            q.push(nxt);
        }
 
        //회전할 수 있는지 판단 후 큐에 담기
        bool canRotate = true;
        logs nxt = cur;
        for (int i = 0; i < 8; i++) {
            
            //중간 통나무에서 상,하,좌,우,대각선 4방향 탐색 - 모든 방향이 범위 안에 있거나, 다른 나무가 없다면 회전 가능
            int bni = nxt.B.x + di[i];
            int bnj = nxt.B.y + dj[i];
 
            if (bni <= 0 || bnj <= 0 || bni > N || bnj > N || map[bni][bnj] == '1') {
                canRotate = false;
                break;
            }
        }
 
        //회전할 수 있다면
        if (canRotate) {
 
            //통나무가 세로로 있는 경우, 가로로 돌리기
            if (nxt.floating == 0) {
                nxt.A.x = nxt.B.x;
                nxt.A.y = nxt.B.y - 1;
                nxt.C.x = nxt.B.x;
                nxt.C.y = nxt.B.y + 1;
                nxt.floating = 1;
            }
            //통나무가 가로로 있는 경우, 세로로 돌리기
            else {
                nxt.A.x = nxt.B.x - 1;
                nxt.A.y = nxt.B.y;
                nxt.C.x = nxt.B.x + 1;
                nxt.C.y = nxt.B.y;
                nxt.floating = 0;
            }
 
            if (!visited[nxt.B.x][nxt.B.y][nxt.floating]) {
                nxt.moveCnt++;
                visited[nxt.B.x][nxt.B.y][nxt.floating] = true;
                q.push(nxt);
            }
        }
    }
    return;
}
 
int main() {
 
    //시작 통나무
    logs st;
    vector<pos> startLogs;
    int startLogsFloat = 0;
 
    //입력
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'B') {
                startLogs.push_back({ i,j });
            }
        }
    }
 
    //첫번째 두번쨰 통나무 열 비교 - 눕혀있는 상태값 찾기
    if (startLogs[1].y - startLogs[0].y == 1) {
        startLogsFloat = 1;
    }
    
    //시작 통나무 = {A통나무 좌표, B통나무 좌표, C통나무 좌표, 눕혀있는 상태, 옮긴 횟수}
    st = { {startLogs[0].x, startLogs[0].y}, {startLogs[1].x, startLogs[1].y}, {startLogs[2].x, startLogs[2].y}, startLogsFloat, 0 };
    visited[st.B.x][st.B.y][startLogsFloat] = true;
    q.push(st);
    bfs();
 
    //출력
    cout << res;
}

 

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

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

[C++] 백준 2511 - 카드놀이  (0) 2020.04.30
[C++] 백준 6087 - 레이저 통신  (0) 2020.04.30
[C++] 백준 2174 - 로봇 시뮬레이션  (0) 2020.04.30
[C++] 백준 3987 - 보이저 1호  (0) 2020.04.30
[C++] 백준 2437 - 저울  (2) 2020.04.30

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

 

2174번: 로봇 시뮬레이션

문제 가로 A(1≤A≤100), 세로 B(1≤B≤100) 크기의 땅이 있다. 이 땅 위에 로봇들이 N(1≤N≤100)개 있다. 로봇들의 초기 위치는 x좌표와 y좌표로 나타난다. 위의 그림에서 보듯 x좌표는 왼쪽부터, y좌표

www.acmicpc.net

<풀이>

1. 주어진 입력 값들을 이해하기 쉽게 정리한다.

2. 명령하나씩 실행시키고, 결과를 출력한다.

​

<해법>

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
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
#include <iostream>
using namespace std;
 
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
//가로,세로,로봇 개수,명령 개수
int A, B, N, M;
 
//로봇이 움직이는 맵
int map[102][102];
//로봇마다 정보(행,열,방향)
int robotInfo[101][3];
 
bool crash = false;
 
bool simulation(int id, char cmd, int cmdCnt) {
 
    //명령내릴 로봇 위치,방향 저장
    int tmpi = robotInfo[id][0];
    int tmpj = robotInfo[id][1];
    int tmpDir = robotInfo[id][2];
 
    map[tmpi][tmpj] = 0;
 
    //명령 반복 횟수만큼 반복
    while (cmdCnt--) {
        if (cmd == 'L') {
            if (tmpDir == 0) {
                tmpDir = 3;
            }
            else {
                tmpDir--;
            }
        }
        else if (cmd == 'R') {
            if (tmpDir == 3) {
                tmpDir = 0;
            }
            else {
                tmpDir++;
            }
        }
        else {
            tmpi += di[tmpDir];
            tmpj += dj[tmpDir];
 
            //벽에 충돌한 경우
            if (tmpi <= 0 || tmpj <= 0 || tmpi > A || tmpj > B) {
                cout << "Robot " << id << " crashes into the wall" << "\n";
                return true;
            }
 
            //다른 로봇에 충돌한 경우
            if (map[tmpi][tmpj] != 0) {
                cout << "Robot " << id << " crashes into robot " << map[tmpi][tmpj] << "\n";
                return true;
            }
        }
    }
 
    //충돌이 발생하지 않았을 경우, 로봇위치 변경
    map[tmpi][tmpj] = id;
 
    robotInfo[id][0] = tmpi;
    robotInfo[id][1] = tmpj;
    robotInfo[id][2] = tmpDir;
 
    return false;
}
 
int main() {
 
    //1.입력
    cin >> B >> A >> N >> M;
    for (int i = 1; i <= N; i++) {
        int tmpi, tmpj, tmpDir;
        char tmp;
 
        cin >> tmpj >> tmpi >> tmp;
 
        if (tmp == 'N') {
            tmpDir = 0;
        }
        else if (tmp == 'E') {
            tmpDir = 1;
        }
        else if (tmp == 'S') {
            tmpDir = 2;
        }
        else {
            tmpDir = 3;
        }
 
        //배열index 조정
        robotInfo[i][0] = (A + 1) - tmpi;
        robotInfo[i][1] = tmpj;
        robotInfo[i][2] = tmpDir;
 
        map[robotInfo[i][0]][robotInfo[i][1]] = i;
    }
    
    //2.명령 수행
    for (int i = 1; i <= M; i++) {
        int id, cmdCnt;
        char cmd;
        cin >> id >> cmd >> cmdCnt;
 
        if (!crash) {
            crash = simulation(id, cmd, cmdCnt);
        }
    }
 
    if (!crash) {
        cout << "OK" << "\n";
    }
 
    return 0;
}

 

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

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

[C++] 백준 6087 - 레이저 통신  (0) 2020.04.30
[C++] 백준 1938 - 통나무 옮기기  (0) 2020.04.30
[C++] 백준 3987 - 보이저 1호  (0) 2020.04.30
[C++] 백준 2437 - 저울  (2) 2020.04.30
[C++] 백준 1992 - 쿼드트리  (0) 2020.04.27

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

 

3987번: 보이저 1호

문제 보이저 1호는 1977년에 발사된 NASA의 태양계 무인 탐사선이다. 현재 보이저 1호는 태양권덮개 (헬리오시스)에 있다. 보이저 1호와 같이 오랜 기간동안 활동하는 탐사선은 경로를 항성계를 만날 때 마다 라디오 시그널 메시지를 이용해서 기록하고 있다. 항성계를 N * M개의 직사각형으로 나누어져 있는 N행 M열의 직사각형 그리드라고 생각해보자. 각 칸은 행성, 블랙홀을 포함할 수 있으며, 비어있을 수도 있다. 탐사선은 인접한 네 칸(위, 아래, 오

www.acmicpc.net

<풀이>

1. 항성계를 입력 받고, 시작점부터 4방향(동,서,남,북) 차례차례 시그널을 보낸다.

2. 각 방향마다 시그널이 어떻게 가는지 구현하고, 결과를 저장한다.

3. 결과를 출력한다.

​

<해법>

1. 시그널이 무한히 전파될 수 있는 경우 구하는 방법.

=> 시그널이 '이전에 방문했던 좌표'를 '똑같은 방향'으로 방문했을 때, 시그널이 무한히 전파될 수 있는 경우가 됩니다.(코드의 visited배열을 사용)

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
#include <iostream>
#include <cstring>
using namespace std;
 
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
int changeDir_1[] = { 1,0,3,2 };
int changeDir_2[] = { 3,2,1,0 };
 
int N, M;
char map[502][502];
bool visited[502][502][4];
int si, sj;
 
char resDir[] = { 'U','R','D','L' };
int resTime = 0;
int resDirIndex;
bool isVoyager = false;
 
int main() {
 
    //입력
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
        }
    }
    cin >> si >> sj;
 
    //시작점부터 4방향 탐색
    for (int i = 0; i < 4; i++) {
 
        //좌표, 방향, 시간, 방문 초기화
        memset(visited, false, sizeof(visited));
        int ni = si;
        int nj = sj;
        int dir = i;
        int time = 1;
        visited[si][sj][i] = true;
 
        while (true) {
 
            ni += di[dir];
            nj += dj[dir];
 
            //다음 시그널 위치가 범위를 넘어섰거나, 블랙홀을 만났을 경우 - 종료
            if (ni <= 0 || nj <= 0 || ni > N || nj > M || map[ni][nj] == 'C') {
                break;
            }
 
            //다음 시그널의 위치가 이전에 같은 방향으로 방문한적이 있을 경우 - 종료(Voyager)
            if (visited[ni][nj][dir]) {
                isVoyager = true;
                break;
            }
 
            //다음 시그널의 위치가 '.', '/', '\'일 경우 - 진행
            if (map[ni][nj] == '.') {
                
            }
            else if (map[ni][nj] == '/') {
                dir = changeDir_1[dir];
            }
            else {
                dir = changeDir_2[dir];
            }
            visited[ni][nj][dir] = true;
            time++;
        }
 
        //결과 저장
        if (isVoyager) {
            resDirIndex = i;
            break;
        }
        else {
            if (time > resTime) {
                resTime = time;
                resDirIndex = i;
            }
        }
    }
 
    //결과 출력
    if (isVoyager) {
        cout << resDir[resDirIndex] << "\n" << "Voyager";
    }
    else {
        cout << resDir[resDirIndex] << "\n" << resTime;
    }
}
 

 

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

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

[C++] 백준 1938 - 통나무 옮기기  (0) 2020.04.30
[C++] 백준 2174 - 로봇 시뮬레이션  (0) 2020.04.30
[C++] 백준 2437 - 저울  (2) 2020.04.30
[C++] 백준 1992 - 쿼드트리  (0) 2020.04.27
[C++] 백준 2436 - 공약수  (0) 2020.04.27

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

 

2437번: 저울

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓�

www.acmicpc.net

<풀이>

1. 저울추를 입력받는다.

2. 저울추를 정렬한다.

3. 결과값을 구하고 출력한다.

​

<해법>

1. 측정할 수 없는 무게를 구하는 방법.

=> 만약 내가 가지고 있는 저울추들로 1~K무게를 모두 만들 수 있다고 가정합니다. 다음 저울추(L)가 K무게 보다 같거나 작다면, 다음 저울추로 (1+L)~(K+L)무게를 모두 만들 수 있습니다. 그렇다면 다음 저울추까지 포함하면 1~(K+L)무게를 모두 만들 수 있는 것이 됩니다.

 

간단하게 예를 들면 가지고 있는 저울추들로 1,2,3,4 무게를 만들 수 있다고 해보겠습니다.

다음 저울추가 5라면 5,6,7,8,9 무게를 만들 수 있을 것이다. 따라서, 1~9 무게를 모두 만들 수 있습니다.

하지만, 다음 저울추가 6라면 6,7,8,9,10 무게를 만들 수 있게되어 무게 5는 측정을 하지 못합니다.

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
#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int arr[1000];
 
int main() {
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    //정렬
    sort(arr, arr + N);
    
    //결과값 구하기
    int res = 1;
    for (int i = 0; i < N; i++) {
        if (arr[i] > res) {
            break;
        }
        res += arr[i];
    }
 
    //출력
    cout << res;
}

 

수학적인 사고에 대해 알아볼 수 있는 문제였습니다.

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

[C++] 백준 2174 - 로봇 시뮬레이션  (0) 2020.04.30
[C++] 백준 3987 - 보이저 1호  (0) 2020.04.30
[C++] 백준 1992 - 쿼드트리  (0) 2020.04.27
[C++] 백준 2436 - 공약수  (0) 2020.04.27
[C++] 백준 2559 - 수열  (0) 2020.04.27

+ Recent posts

티스토리툴바