어흥
[백준 6087] 레이저 통신 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/6087
1. 주의할 점
- BFS를 통해 구현하며, 어떤 방향을 통해서 왔는지 확인해줘야 한다. -> Check[100][100][4]
- 이동을 하면서, 직전에 어떤 방향에서 왔는지 기억해야 한다
2. 구현
- X,Y,Dir(직전에 어떤 방향이었는지)를 담는 구조체를 사용한다
- BFS를 통해 움직이며 직전 이동 방향과 다음 방향이 일치하지 않는 경우 거울을 설치했다고 가정한다
- 직전 이동 방향과 다음 방향이 일치 -> 거울 사용 X
- 거울을 사용한 경우, 다음으로 이동하려는 칸의 Check[Y][X][어떤 방향을 통해 왔는지] 의 값이 현재 위치의 Check값보다 2 이상 크다면 이동한다
- 거울을 사용하지 않는 경우, 다음으로 이동하려는 칸의 Check값이 현재 Check값보다 크다면 이동한다
#define MAX 987654321
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
char arr[100][100];
int check[100][100][4]; //현 지점까지 필요한 거울의 최소 수, [4]: 직전에 어떤 방향에서 왔는지
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int row, col, sx = -1, sy;
struct info {
int x, y, dir;
};
info tmp;
int main() {
cin >> col >> row;
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++) {
cin >> arr[i][j];
for(int k=0;k<4;k++)
check[i][j][k] = MAX;
if (arr[i][j] == 'C' && sx == -1) {
sx = j;
sy = i;
arr[i][j] = '.';
for (int k = 0; k < 4; k++)
check[i][j][k] = 0;
}
}
queue<info> q;
tmp.x = sx;
tmp.y = sy;
for (int k = 0; k < 4; k++) {
tmp.dir = k;
q.push(tmp);
}
int result = MAX;
while (!q.empty()) {
int cx = q.front().x;
int cy = q.front().y;
int cd = q.front().dir;
q.pop();
if (arr[cy][cx] == 'C') {
result = min(result, check[cy][cx][cd]);
continue;
}
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx >= 0 && ny >= 0 && nx < col && ny<row && arr[ny][nx] != '*') {
if (i != cd && check[ny][nx][i] > check[cy][cx][cd] + 1) { //거울 사용
check[ny][nx][i] = check[cy][cx][cd] + 1;
tmp.x = nx;
tmp.y = ny;
tmp.dir = i;
q.push(tmp);
}
else if (i == cd && check[ny][nx][cd] > check[cy][cx][cd]) { //거울 사용x
check[ny][nx][cd] = check[cy][cx][cd];
tmp.x = nx;
tmp.y = ny;
tmp.dir = i;
q.push(tmp);
}
}
}
}
cout << result;
system("pause");
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 8972] 미친 아두이노 (C++) (0) | 2020.04.03 |
---|---|
[백준 11401] 이항 계수 3 (C++) (0) | 2020.04.02 |
[백준 4485] 녹색 옷 입은 애가 젤다지? (C++) (0) | 2020.03.31 |
[백준 17090] 미로 탈출하기 (C++) (0) | 2020.03.31 |
[백준 11779] 최소비용 구하기 2 (C++) (0) | 2020.03.30 |
Comments