정말 늪같은 챕터였다.. 문제도 많고.. 어려웠어..
하지만 그만큼 많은 걸 배웠다. 근데 제발 시간을 재면서 풀자.
한번 매달리면 거의 하루종일 그 문제만 쳐다보는데.. 끈기는 좋지만
효율이 안 나온다. 똑똑하게 공부하자.
정리 시작!
-
* 벽 부수고 이동하기 (mid) : 벽을 하나까지 부술 수 있는 조건에서 최단 경로를 구하는 문제다.
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로��
www.acmicpc.net
- 벽을 부쉈는지, 안 부쉈는지까지 생각해서 기록해줘야 한다는 것이 포인트였다.
#include <iostream>
#include <cstdio>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
int a[1000][1000];
int dist[1000][1000][2];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%1d", &a[i][j]);
}
}
queue<tuple<int, int, int>> q;
q.push(make_tuple(0, 0, 0));
dist[0][0][0] = 1;
while (!q.empty()) {
int x, y, z;
tie(x, y, z) = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (a[nx][ny] == 0 && dist[nx][ny][z] == 0) {
dist[nx][ny][z] = dist[x][y][z] + 1;
q.push(make_tuple(nx, ny, z));
}
if (z == 0 && a[nx][ny] == 1 && dist[nx][ny][z + 1] == 0) {
dist[nx][ny][z+1] = dist[x][y][z] + 1;
q.push(make_tuple(nx, ny, z+1));
}
}
}
if (dist[n - 1][m - 1][0] != 0 && dist[n - 1][m - 1][1] != 0) {
cout << min(dist[n - 1][m - 1][0], dist[n - 1][m - 1][1]);
}
else if (dist[n - 1][m - 1][0] != 0) {
cout << dist[n - 1][m - 1][0];
}
else if (dist[n - 1][m - 1][1] != 0) {
cout << dist[n - 1][m - 1][1];
}
else {
cout << -1;
}
cout << '\n';
return 0;
}- 이동하려는 칸이 빈칸일 때는 벽을 부쉈든, 안 부쉈든 상관 없이 이동할 수 있다.
- 하지만 이동하려는 칸이 벽일 때는 벽을 이미 한번 부쉈다면 이동할 수 없다. 부순 경험이 없어야 이동이 가능하다.
* 벽 부수고 이동하기 4 (mid) : 벽이 있는 곳을 부쉈을 때 각각 이동할 수 있는 칸을 구하는 문제다.
16946번: 벽 부수고 이동하기 4
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 �
www.acmicpc.net
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <tuple>
#include <set>
using namespace std;
int a[1000][1000], b[1000][1000];
bool visited[1000][1000];
vector<int> gc;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int n, m;
int g = 0;
void bfs(int x, int y) {
queue<pair<int, int>> q;
q.push(make_pair(x, y));
visited[x][y] = true;
b[x][y] = g;
int cnt = 1;
while (!q.empty()) {
int tx, ty;
tie(tx, ty) = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = tx + dx[i];
int ny = ty + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (a[nx][ny] == 0 && visited[nx][ny] == false) {
q.push(make_pair(nx, ny));
visited[nx][ny] = true;
b[nx][ny] = g;
cnt += 1;
}
}
}
gc.push_back(cnt);
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%1d", &a[i][j]);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == 0 && visited[i][j] == false) {
bfs(i, j);
g += 1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == 0) {
cout << 0;
}
else {
set<int> near;
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (a[nx][ny] == 0) {
near.insert(b[nx][ny]);
}
}
int ans = 1;
for (int s : near) {
ans += gc[s];
}
cout << ans % 10;
}
}
cout << '\n';
}
return 0;
}- 먼저 벽을 안 부순 상태에서 빈칸을 그룹지어 개수를 세준다. 그리고 각각의 벽을 깬다고 했을 때, 이동 가능한 그룹을 기록해주고 그 합을 구한 뒤에, 1을 더해주면 된다. (벽이 있던 자리도 이동할 수 있으니까)
- set 컨테이너가 정말 꿀이다. set은 중복된 값을 받지 않고, 알아서 정렬까지 해준다. 여러모로 요긴하게 쓸 수 있으니 잘 기억해두자.
* 벽 부수고 이동하기 2 (mid) : 1의 확장판 문제라고 보면 되겠다. 벽을 부술 수 있는 횟수를 입력 받는다.
14442번: 벽 부수고 이동하기 2
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
www.acmicpc.net
#include <iostream>
#include <cstdio>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
int a[1000][1000];
int dist[1000][1000][11];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int main()
{
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%1d", &a[i][j]);
}
}
queue<tuple<int, int, int>> q;
q.push(make_tuple(0, 0, 0));
dist[0][0][0] = 1;
while (!q.empty()) {
int x, y, z;
tie(x, y, z) = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (a[nx][ny] == 0 && dist[nx][ny][z] == 0) {
dist[nx][ny][z] = dist[x][y][z] + 1;
q.push(make_tuple(nx, ny, z));
}
if (z+1 <= k && a[nx][ny] == 1 && dist[nx][ny][z + 1] == 0) {
dist[nx][ny][z + 1] = dist[x][y][z] + 1;
q.push(make_tuple(nx, ny, z + 1));
}
}
}
int ans = -1;
for (int i = 0; i <= k; i++) {
if (dist[n - 1][m - 1][i] != 0) {
if (ans == -1 || ans > dist[n - 1][m - 1][i]) {
ans = dist[n - 1][m - 1][i];
}
}
}
cout << ans << '\n';
return 0;
}- 한번 밖에 못 부쉈던 벽을 k번 부술 수 있다. 적절히 맞춰서 사이즈를 늘려주면 된다.
* 벽 부수고 이동하기 3 (mid) : 이제는 낮밤 조건까지 등장했다. 낮에만 벽을 깰 수 있다.
16933번: 벽 부수고 이동하기 3
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
www.acmicpc.net
#include <iostream>
#include <cstdio>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
int a[1000][1000];
int dist[1000][1000][11][2];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int main()
{
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%1d", &a[i][j]);
}
}
queue<tuple<int, int, int, int>> q;
q.push(make_tuple(0, 0, 0, 0));
dist[0][0][0][0] = 1;
while (!q.empty()) {
int x, y, z, night;
tie(x, y, z, night) = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (a[nx][ny] == 0 && dist[nx][ny][z][1 - night] == 0) {
dist[nx][ny][z][1 - night] = dist[x][y][z][night] + 1;
q.push(make_tuple(nx, ny, z, 1 - night));
}
if (night == 0 && z+1 <= k && a[nx][ny] == 1 && dist[nx][ny][z + 1][1-night] == 0) {
dist[nx][ny][z + 1][1-night] = dist[x][y][z][night] + 1;
q.push(make_tuple(nx, ny, z + 1, 1 - night));
}
}
if (dist[x][y][z][1 - night] == 0) {
dist[x][y][z][1 - night] = dist[x][y][z][night] + 1;
q.push(make_tuple(x, y, z, 1 - night));
}
}
int ans = -1;
for (int i = 0; i <= k; i++) {
for (int j = 0; j < 2; j++) {
if (dist[n - 1][m - 1][i][j] != 0) {
if (ans == -1 || ans > dist[n - 1][m - 1][i][j]) {
ans = dist[n - 1][m - 1][i][j];
}
}
}
}
cout << ans << '\n';
return 0;
}- 마찬가지로 낮, 밤을 기록하는 공간을 추가해주면 된다. 이동하지 않는 선택지도 있다는 것에 주의해야 한다.
* 움직이는 미로 탈출 (high) : 벽이 1초에 한 칸씩 아래로 내려오는 미로를 탈출할 수 있는지 구하는 문제다.
16954번: 움직이는 미로 탈출
욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽
www.acmicpc.net
- 겁나게 해맸는데, 코드가 의외로 길지 않아서 놀랐다. 예외 검사를 어떤 방식으로 하느냐가 포인트였다.
#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
#include <string>
using namespace std;
bool check[8][8][9];
int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0, 0 };
int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1, 0 };
int main()
{
vector<string> a(8);
for (int i = 0; i < 8; i++) {
cin >> a[i];
}
queue<tuple<int, int, int>> q;
check[7][0][0] = true;
q.push(make_tuple(7, 0, 0));
bool ans = false;
while (!q.empty()) {
int x, y, z;
tie(x, y, z) = q.front();
q.pop();
if (x == 0 && y == 7) { ans = true; break; }
for (int i = 0; i < 9; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
int nz = min(z + 1, 8);
if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8) continue;
if (nx - z >= 0 && a[nx - z][ny] == '#') continue;
if (nx - z - 1 >= 0 && a[nx - z - 1][ny] == '#') continue;
if (check[nx][ny][nz] == false) {
check[nx][ny][nz] = true;
q.push(make_tuple(nx, ny, nz));
}
}
}
cout << ans << '\n';
return 0;
}- 우선 출발 지점인 (7,0)을 큐에 넣고 while 문을 돌린다. 소요 시간을 같이 넣어주는데, 8*8 사이즈 판이기 때문에 8초 이상이 되면 모든 벽이 사라지므로 차이가 없다. 이를 생각해서 값을 받아준다.
- 먼저 현재 위치(x,y)까지 소요된 시간(z)을 이동해야 할 좌표값(nx,ny)의 nx에서 빼준다. 그럼 z초 뒤에 (nx,ny)로 올 값을 알 수 있다. 이 값이 벽이라면 이동할 수 없는 곳이므로 건너 뛴다.
- 다음으로 z+1를 빼줘서 한번 더 검사를 하는데, 이는 캐릭터가 이동을 하고 난 뒤에 벽이 움직인다고 했기 때문에 그것까지 생각해준 것이다. 그것까지 이상이 없고, 방문하지 않은 곳이라면 이동할 수 있는 곳이다.
* 탈출 (mid) : 고슴도치가 물을 피해 비버의 굴로 이동할 수 있는 가장 빠른 시간을 구하는 문제다.
3055번: 탈출
문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치��
www.acmicpc.net
- 물의 이동을 피해 목적지로 가야한다. 동시에 생각해주기는 너무 번거로우므로, 물의 이동과 고슴도치의 이동을 따로 생각해서 풀어봤다.
#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
#include <string>
using namespace std;
int water[50][50];
int checkS[50][50];
int dx[] = { -1, 1, 0, 0};
int dy[] = { 0, 0, -1, 1};
int main()
{
int r, c;
cin >> r >> c;
vector<string> a(r);
queue<pair<int, int>> qw;
queue<tuple<int, int, int>> qs;
for (int i = 0; i < r; i++) {
cin >> a[i];
for (int j = 0; j < c; j++) {
water[i][j] = -1;
checkS[i][j] = -1;
if (a[i][j] == '*') {
qw.push(make_pair(i, j));
water[i][j] = 0;
}
if (a[i][j] == 'S') {
qs.push(make_tuple(i, j, 0));
checkS[i][j] = 0;
}
}
}
while (!qw.empty()) {
int x, y;
tie(x, y) = qw.front(); qw.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
if (a[nx][ny] == '.' || a[nx][ny] == 'S') {
if (water[nx][ny] == -1) {
water[nx][ny] = water[x][y] + 1;
qw.push(make_pair(nx, ny));
}
}
}
}
int ans = -1;
while (!qs.empty()) {
int x, y, m;
tie(x, y, m) = qs.front(); qs.pop();
if (a[x][y] == 'D') {
if (ans == -1 || ans > m) {
ans = m; continue;
}
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
if (a[nx][ny] == '.' || a[nx][ny] == 'D') {
if (water[nx][ny] == -1 || m + 1 < water[nx][ny]) {
if (checkS[nx][ny] == -1) {
checkS[nx][ny] = m + 1;
qs.push(make_tuple(nx, ny, m + 1));
}
}
}
}
}
if (ans > 0) cout << ans << '\n';
else cout << "KAKTUS" << '\n';
return 0;
}- 먼저 물이 도달하는 시간을 기록해줬다. 물이 이동할 수 없는 곳을 제외해서 생각해준다. 다음으로 고슴도치가 이동하는데, 해당 위치에 물이 도달하는 시간보다 고슴도치가 도달하는 시간이 작아야 더 빨리 도착한 것이다.
- 이런 방식으로 도착지에 도달할 수 있는 최소 시간을 구해주면 된다.
* 아기 상어 (high) : 아기 상어가 엄마 상어의 도움 없이 물고기를 잡아먹을 수 있는 시간을 구하는 문제다.
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가��
www.acmicpc.net
- 조건이 많다. 처음 아기 상어의 크기는 2다. 자신의 크기보다 작은 물고기만 먹을 수 있다. 같은 크기의 물고기가 있는 곳은 지나가기만 할 수 있다. 먹을 수 있는 물고기가 1마리면 그 물고기를 먹으러 가고, 1마리보다 많으면 가장 거리가 가까운 물고기를 먹으러 간다. 거리가 가까운 물고기가 많다면 가장 위, 가장 왼쪽의 물고기를 먹는다.
- 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다. 이때 몇 초동안 엄마 상어의 도움 없이 물고기를 먹을 수 있는지 구하는 문제다.
- 일단 이런 문제가 나오면.. 조건을 잘 정리하자. 너무 무턱대고 푸는 안 좋은 습관이 있다. 그래도 얼추 되긴 하지만, 정말 어려운 문제가 나왔을 때 이런 식의 풀이가 적응이 되어 있으면 디버깅을 제대로 하기가 힘들다. 운좋게 한번에 되는 경우는 정말 드물기 때문에.. 조건을 잘 정리하고 방법을 생각해서 코딩을 하는 습관을 기르자.
#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
tuple<int, int, int> bfs(vector<vector<int>> &a, int x, int y, int size) {
int n = a.size();
vector<tuple<int, int, int>> ans;
vector<vector<int>> d(n, vector<int>(n, -1));
queue<pair<int, int>> q;
q.push(make_pair(x, y));
d[x][y] = 0;
while (!q.empty()) {
tie(x, y) = q.front();
q.pop();
for (int k = 0; k<4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < n && d[nx][ny] == -1) {
bool ok = false;
bool eat = false;
if (a[nx][ny] == 0) {
ok = true;
}
else if (a[nx][ny] < size) {
ok = eat = true;
}
else if (a[nx][ny] == size) {
ok = true;
}
if (ok) {
q.push(make_pair(nx, ny));
d[nx][ny] = d[x][y] + 1;
if (eat) {
ans.push_back(make_tuple(d[nx][ny], nx, ny));
}
}
}
}
}
if (ans.empty()) {
return make_tuple(-1, -1, -1);
}
sort(ans.begin(), ans.end());
return ans[0];
}
int main() {
int n;
cin >> n;
vector<vector<int>> a(n, vector<int>(n, 0));
int x, y;
for (int i = 0; i<n; i++) {
for (int j = 0; j<n; j++) {
cin >> a[i][j];
if (a[i][j] == 9) {
tie(x, y) = make_pair(i, j);
a[i][j] = 0;
}
}
}
int ans = 0;
int size = 2;
int exp = 0;
while (true) {
int nx, ny, dist;
tie(dist, nx, ny) = bfs(a, x, y, size);
if (dist == -1) break;
a[nx][ny] = 0;
ans += dist;
exp += 1;
if (size == exp) {
size += 1;
exp = 0;
}
tie(x, y) = make_pair(nx, ny);
}
cout << ans << '\n';
return 0;
}
- 먼저 아기 상어의 위치를 기록하고 계산의 편의를 위해 9를 0으로 바꿔준다.
- 현재 위치에서 bfs를 돌려준다. 이동할 수 있는 조건, 먹을 수 있는 조건을 체크한다. 이동할 수 있는 조건은 빈 칸일 때와 아기 상어보다 같거나 작은 크기의 물고기가 있을 때다. 먹을 수 있는 조건은 아기 상어보다 작은 크기의 물고기가 있을 때다. 이동할 수 있다면 큐에 좌표를 넣어주고, dist를 업데이트 해준다. 거기에 먹을 수까지 있다면 소요된 시간과 좌표를 따로 저장해준다.
- bfs가 돌면서 먹을 수 있는 물고기를 모두 저장했을 것이다. 이를 소요된 시간, 좌표 순으로 저장한 것은 문제의 조건에서 이동 시간이 같으면 가장 위쪽, 왼쪽에 있는 물고기를 먹어야 한다고 했기 때문이다. 저장된 tuple을 sort하고 가장 첫번째 값을 취하면 그것이 먹을 수 있는 물고기의 정보다.
- 이를 소요시간에 누적해서 더해주고, 잡아 먹은 횟수와 사이즈를 조건에 맞게 업데이트 해주면서 반복해주면 된다.
* 레이저 통신 (mid) : 레이저로 통신하기 위해 거울을 최소 몇개 놓아야 하는지 구하는 문제다.
6087번: 레이저 통신
문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위
www.acmicpc.net
- 우선은 꾸역꾸역 맞춘 내 코드부터 정리해본다. 정답 코드와 비교해서 보면 좋을 것 같아서..
#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
#include <vector>
#include <string>
using namespace std;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int main() {
int w, h;
cin >> w >> h;
vector<string> a(h);
int x1 = -1, y1, x2, y2;
for (int i = 0; i < h; i++) {
cin >> a[i];
for (int j = 0; j < w; j++) {
if (a[i][j] == 'C') {
if (x1 == -1) tie(x1, y1) = make_pair(i, j);
else tie(x2, y2) = make_pair(i, j);
}
}
}
queue< tuple<int, int, int> > q;
int mir[100][100][4];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
for (int k = 0; k < 4; k++) {
mir[i][j][k] = -1;
}
}
}
q.push(make_tuple(x1, y1, -1));
for (int i = 0; i < 4; i++) mir[x1][y1][i] = 0;
while (!q.empty()) {
int x, y, d;
tie(x, y, d) = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
if (a[nx][ny] != '*') {
if (d == -1) {
mir[nx][ny][i] = mir[x][y][i];
q.push(make_tuple(nx, ny, i));
}
else {
if (d == i) {
if (mir[nx][ny][i] == -1 || mir[nx][ny][i] > mir[x][y][d]) {
mir[nx][ny][i] = mir[x][y][d];
q.push(make_tuple(nx, ny, i));
}
}
else {
if (mir[nx][ny][i] == -1 || mir[nx][ny][i] > mir[x][y][d] + 1) {
mir[nx][ny][i] = mir[x][y][d] + 1;
q.push(make_tuple(nx, ny, i));
}
}
}
}
}
}
int ans = -1;
for (int i = 0; i < 4; i++) {
if (mir[x2][y2][i] != -1) {
if (ans == -1 || ans > mir[x2][y2][i])
ans = mir[x2][y2][i];
}
}
cout << ans << '\n';
return 0;
}
- 길이를 기록할 때 어떤 방향에서 온 값인지를 생각해줬다. 출발값은 따로 방향이 없었으니 -1로 뒀다.
- d가 -1일 때, 즉 처음 레이저를 쏠 때는 출발점이기에 따로 거울이 필요하지 않으므로 이동하는 값에 모두 0을 넣어줬다. d가 -1이 아니고, d와 같은 방향으로 레이저를 쏠 때 이전 mir 값을 그대로 넣어준다. d와 다른 방향이면 이전 mir값에 1을 더해준다. 거울이 하나 추가된 것이다.
- 이런 식으로 bfs를 돌려주고, d[x2][y2][0] ~ d[x2][y2][3] 중 최솟값을 구해주면 된다.
- 나쁘지 않지만, 굳이 방향을 기록해줄 필요가 있나 싶다. 값을 기록할 때 조건에 맞게 뻗어나가는 방향에 쭉 똑같은 값을 넣어주면 된다. 정답 코드를 참고해서 한번 더 풀어봤다.
#include <iostream>
#include <queue>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int main()
{
int w, h;
cin >> w >> h;
vector<string> a(h);
int x1 = -1, y1, x2, y2;
for (int i = 0; i < h; i++) {
cin >> a[i];
for (int j = 0; j < w; j++) {
if (a[i][j] == 'C') {
if (x1 == -1) {
x1 = i; y1 = j;
}
else {
x2 = i; y2 = j;
}
}
}
}
vector< vector<int> > d(h, vector<int>(w, -1));
queue< pair<int, int> > q;
q.push(make_pair(x1, y1));
d[x1][y1] = 0;
while (!q.empty()) {
int x, y;
tie(x, y) = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
while (nx >= 0 && nx < h && ny >= 0 && ny < w) {
if (a[nx][ny] == '*') break;
if (d[nx][ny] == -1) {
d[nx][ny] = d[x][y] + 1;
q.push(make_pair(nx, ny));
}
nx += dx[i]; ny += dy[i];
}
}
}
cout << d[x2][y2] - 1 << '\n';
return 0;
}- d에 기록되는 값은 거울의 개수가 아니라 선분의 개수라고 할 수 있다. 거울의 개수는 선분의 개수에 1만 빼주면 된다. 그림을 그려보면 쉽게 알 수 있다. 훨씬 간단하게 문제가 풀린다.
* 소수 경로 (mid) : 4자리 소수의 상태를 유지하면서 자리수를 하나씩 바꿔 가며 원하는 소수값에 최소 횟수로 도달하는 문제다.
1963번: 소수 경로
문제 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응
www.acmicpc.net
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <stdlib.h>
using namespace std;
bool prime[10000];
int main() {
for (int i = 2; i*i < 10000; i++) {
if (prime[i] == false) {
for (int j = i * 2; j < 10000; j += i) {
prime[j] = true;
}
}
}
int T;
cin >> T;
for (int i = 0; i < T; i++) {
string from, to;
cin >> from >> to;
queue< pair<string, int> > q;
vector< vector<bool> > check(10000, vector<bool>(10000, false));
q.push(make_pair(from, 0));
check[atoi(from.c_str())][0] = true;
bool pos = false;
while (!q.empty()) {
string x = q.front().first;
int cnt = q.front().second;
q.pop();
if (atoi(x.c_str()) == atoi(to.c_str())) {
cout << cnt << '\n';
pos = true;
break;
}
for (int i = 0; i < 4; i++) {
char t = x[i];
for (int j = 0; j <= 9; j++) {
if (i == 0 && j == 0) continue;
if (t - '0' == j) continue;
x[i] = j + '0';
if (prime[atoi(x.c_str())] == false && check[atoi(x.c_str())][cnt+1] == false) {
check[atoi(x.c_str())][cnt+1] = true;
q.push(make_pair(x,cnt+1));
}
}
x[i] = t;
}
}
if (!pos) cout << "Impossible" << '\n';
}
return 0;
}
- 우선 에라토스테네스의 체를 이용해 범위 안의 소수값을 체크해준다.
- 자리수를 하나씩 바꿔야 하므로 string 값으로 숫자를 입력 받아 한 자리씩 바꿔주고, 이를 정수형으로 변환했을 때 소수값인지를 확인하면서 풀어주면 된다.
* 적록색약 (mid) : 일반 사람과 적록색약인 사람이 구분할 수 있는 그룹의 수를 각각 구하는 문제다.
10026번: 적록색약
문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(
www.acmicpc.net
- 적록색약은 빨강색과 초록색의 차이를 느끼지 못해 같은 색으로 인식한다. 따라서 일반 사람은 똑같이 bfs를 해주면 되고, 적록색약인 사람은 빨강과 초록을 똑같은 것으로 인식하도록 bfs를 해주면 된다.
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <tuple>
using namespace std;
int n;
bool check[100][100];
bool check2[100][100];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
void bfs(vector<string> &a, int tx, int ty) {
queue<pair<int, int> > q;
q.push(make_pair(tx, ty));
check[tx][ty] = true;
char color = a[tx][ty];
while (!q.empty()) {
int x, y;
tie(x, y) = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (color == a[nx][ny] && check[nx][ny] == false) {
q.push(make_pair(nx, ny));
check[nx][ny] = true;
}
}
}
}
void bfs2(vector<string> &a, int tx, int ty) {
queue<pair<int, int> > q;
q.push(make_pair(tx, ty));
check2[tx][ty] = true;
char color = a[tx][ty];
while (!q.empty()) {
int x, y;
tie(x, y) = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (color == 'R' || color == 'G') {
if (a[nx][ny] == 'R' || a[nx][ny] == 'G') {
if (check2[nx][ny] == false) {
q.push(make_pair(nx, ny));
check2[nx][ny] = true;
}
}
}
else {
if (color == a[nx][ny] && check2[nx][ny] == false) {
q.push(make_pair(nx, ny));
check2[nx][ny] = true;
}
}
}
}
}
int main() {
cin >> n;
vector<string> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int sec = 0, sec2 = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (check[i][j] == false) {
bfs(a,i,j);
sec += 1;
}
if (check2[i][j] == false) {
bfs2(a, i, j);
sec2 += 1;
}
}
}
cout << sec << ' ' << sec2 << '\n';
return 0;
}
* 4 연산 (mid) : 주어진 연산을 활용해 원하는 값을 만들 수 있는 최소 연산 횟수를 구하는 문제다.
14395번: 4연산
첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아
www.acmicpc.net
- 백트래킹을 써야하나? 했는데 굳이 그럴 필요 없었다. 그냥 조건에 맞는 값인지 체크 해주고, bfs로 계속 확인해주면 된다. 주의할 점은 가능한 값이 10억까지 되기 때문에 배열을 만들기에는 무리가 있다. 이때 아까 배웠던 개꿀 set 컨테이너를 활용하면 배열을 안 만들어도 중복을 확인해줄 수 있다.
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <tuple>
#include <set>
using namespace std;
int main() {
long long s, t;
cin >> s >> t;
if (s == t) {
cout << 0 << '\n';
return 0;
}
else {
queue< pair<long long, string> > q;
set<long long> check;
q.push(make_pair(s,""));
check.insert(s);
while (!q.empty()) {
long long x; string op;
tie(x,op) = q.front(); q.pop();
if (x == t) {
cout << op << '\n';
return 0;
}
int csize;
for (int i = 0; i < 4; i++) {
if (i == 0) {
csize = check.size();
check.insert(x*x);
if (check.size() != csize) {
q.push(make_pair(x*x, op+'*'));
}
}
else if (i == 1) {
csize = check.size();
check.insert(x+x);
if (check.size() != csize) {
q.push(make_pair(x+x, op+'+'));
}
}
else if (i == 2) {
csize = check.size();
check.insert(0);
if (check.size() != csize) {
q.push(make_pair(0, op+'-'));
}
}
else {
if (x == 0) continue;
csize = check.size();
check.insert(1);
if (check.size() != csize) {
q.push(make_pair(1, op+'/'));
}
}
}
}
}
cout << -1 << '\n';
return 0;
}
- set에 연산값을 insert 했을 때 이미 값이 들어가 있으면 사이즈가 안 변할 것이고, 사이즈가 변했다면 값이 들어간 것이므로 큐에 추가해준다. count를 사용해서 해당 값이 들어있는지 확인하는 방법도 있다. set에는 중복이 허용되지 않기 때문에 count 값이 0 아니면 1 밖에 안 나온다.
-
정리하고 보니 엄청 많이 했다...
뭔가 늪에 빠진듯이 오래 끈 느낌이었는데.. 또 끝내고 나니 뿌듯하다.
어떤 이유에 의해 진도를 좀 빨리 나가고 싶어졌다.
진도가 느려진 게 난이도가 올라서 그런 것일 수도 있지만 예전에 비해서 텐션이 떨어진 것도 사실이다.
좀 더 꽉 조여서 빡시게 진도를 나가보려고 한다. 한번 해보자.
정리 끝!
'알고리즘 > 백준 알고리즘 강의' 카테고리의 다른 글
| 백준 알고리즘 중급 - 그리디 알고리즘 - 2 (0) | 2020.08.25 |
|---|---|
| 백준 알고리즘 중급 - 그리디 알고리즘 - 1 (0) | 2020.08.25 |
| 백준 알고리즘 중급 - BFS (연습) - 1 (0) | 2020.08.18 |
| 백준 알고리즘 중급 - 브루트 포스 : 비트마스크 (연습) (0) | 2020.08.14 |
| 백준 알고리즘 중급 - 브루트 포스 : 재귀 (연습) - 2 (0) | 2020.08.08 |
