Study hard
(c++)백준 6087번: 레이저 통신 본문
https://www.acmicpc.net/problem/6087
6087번: 레이저 통신
크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서
www.acmicpc.net
[풀이]
※주의 할 것: 최소 거리를 구하는 게 아니라 거울 개수의 최솟값을 구하는 것!
- bfs 사용
- visited 2차원 배열에 각 좌표까지 가는 데 놓아야 하는 거울 개수의 최솟값을 저장한다.
#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct Mirror {
int x, y;//설치된 거울 좌표
int d;//방향
int mirror;//거울 개수
};
int W, H;
char Map[100][100];
int visited[100][100];
const int dx[] = { -1,1,0,0 };//0:위, 1:아래, 2:왼쪽, 3:오른쪽
const int dy[] = { 0,0,-1,1 };
int startx, starty, destx, desty;
void bfs() {
queue<Mirror>q;
//모든 방향에 대해 큐에 넣어두기
for(int i=0;i<4;i++){
q.push({ startx,starty,i,0 });
}
visited[startx][starty] = 0;
while (!q.empty()) {
int x = q.front().x;
int y = q.front().y;
int d = q.front().d;
int m = q.front().mirror;
q.pop();
for (int i = 0; i < 4; i++) {
//180도 회전은 무시
if ((d == 0 && i == 1) || (i == 0 && d == 1) || (d == 2 && i == 3) || (i == 2 && d == 3))
continue;
int nx = x + dx[i];
int ny = y + dy[i];
int nm = m;
if (nx < 0 || nx >= H || ny < 0 || ny >= W)
continue;
if (Map[nx][ny] != '*') {
//방향이 다를 때
if (d != i)
nm = nm + 1;
//거울의 개수 + 1이 지금까지 구한 최소 거울의 수보다 작으면
if (visited[nx][ny] >= nm) {
visited[nx][ny] = nm;
q.push({ nx,ny,i,nm });
}
}
}
}
}
void solution() {
cin >> W >> H;
string s;
bool isFirstC = true;
for (int i = 0; i < H; i++) {
cin >> s;
for (int j = 0; j < W; j++) {
Map[i][j] = s[j];
if (Map[i][j] == 'C' && isFirstC) {
startx = i, starty = j;
isFirstC = false;
}
else if (Map[i][j] == 'C' && !isFirstC) {
destx = i, desty = j;
}
visited[i][j] = 9999999;
}
}
bfs();
cout << visited[destx][desty] << '\n';
}
int main() {
solution();
return 0;
}
'백준 > bfs, dfs' 카테고리의 다른 글
(c++)백준 10026번: 적록색약 (0) | 2020.09.03 |
---|---|
(c++)백준 1963번: 소수 경로 (0) | 2020.09.02 |
(c++)백준 3055번: 탈출 (0) | 2020.09.01 |
(c++)백준 16954번: 움직이는 미로 탈출 (0) | 2020.09.01 |
(c++)백준 16933번: 벽 부수고 이동하기 3 (0) | 2020.08.31 |