6087 레이저 통신
2019. 8. 13. 17:56ㆍ알고리즘/백준
bfs 문제로 벽이나 외곽을 만날 때까지 거울의 개수를 유지하면서 큐에 넣어준다. 기존 dist보다 작은 값들이 나올 수 있으므로 이 부분도 확인을 해야만 한다
문제: https://www.acmicpc.net/problem/6087
깃허브주소: https://github.com/surinoel/boj/blob/master/6087.cpp
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <queue> | |
#include <tuple> | |
#include <string> | |
#include <cstring> | |
#include <iomanip> | |
#include <iostream> | |
using namespace std; | |
int mat[100][100]; | |
int dist[100][100]; | |
int dx[4] = { 1, -1, 0, 0 }; | |
int dy[4] = { 0, 0, 1, -1 }; | |
int main(void) { | |
ios_base::sync_with_stdio(false); | |
cin.tie(nullptr); | |
int n, m, ex, ey; | |
cin >> m >> n; | |
queue<tuple<int, int, int>> q; | |
memset(dist, -1, sizeof(dist)); | |
for (int i = 0; i < n; i++) { | |
string s; | |
cin >> s; | |
for (int j = 0; j < s.size(); j++) { | |
if (s[j] == 'C') { | |
if (q.empty()) { | |
dist[i][j] = 0; | |
q.push(make_tuple(i, j, 0)); | |
} | |
else { | |
ex = i; | |
ey = j; | |
} | |
mat[i][j] = 2; | |
} | |
else if (s[j] == '*') { | |
mat[i][j] = -1; | |
} | |
} | |
} | |
while (!q.empty()) { | |
int x, y, z; | |
tie(x, y, z) = q.front(); | |
q.pop(); | |
for (int k = 0; k < 4; k++) { | |
int tx = x + dx[k]; | |
int ty = y + dy[k]; | |
while (!(tx < 0 || ty < 0 || tx > n - 1 || ty > m - 1 || mat[tx][ty] == -1)) { | |
if (dist[tx][ty] == -1 || dist[tx][ty] > dist[x][y]) { | |
dist[tx][ty] = z; | |
q.push(make_tuple(tx, ty, z + 1)); | |
tx += dx[k]; | |
ty += dy[k]; | |
} | |
else { | |
break; | |
} | |
} | |
} | |
} | |
cout << dist[ex][ey] << '\n'; | |
return 0; | |
} |
'알고리즘 > 백준' 카테고리의 다른 글
4179 불! (0) | 2019.08.14 |
---|---|
17406 배열 돌리기 4 (0) | 2019.08.13 |
8922 두찌 수열 (0) | 2019.08.12 |
16236 아기 상어 (0) | 2019.08.10 |
17144 미세먼지 안녕 (0) | 2019.08.10 |