BFS를 사용하되, 매 루프마다 한 칸씩 이동하는 대신,
갈 수 있는 만큼 최대한 한 방향으로 이동한다.
또 visited 칸을 저장하는 대신, 한 번 지나간 칸에 대해 해당 칸으로 가기 까지 필요한 거울의 갯수(count)를 기록한다.
즉 count != 0 이라면 한 번 이상 방문한 칸인 셈이다.
BFS를 사용하기 때문에, 어느 칸에 처음 방문했을때 그 칸까지 가는 최단거리(여기서는 최소한으로 사용되는 거울 갯수)를 바로 알 수 있으며, 이러한 성질을 활용해 거울의 갯수를 축적시켜 최종적으로 목적지에 도달할때까지 길을 찾는 방식이다.
(굉장히 다양한 풀이가 존재하지만 이 풀이가 가장 깔끔하고 직관적인 풀이법이라고 생각한다.)
#include <iostream>
#include <queue>
using namespace std;
char grid[101][101];
int count[101][101];
int dirs[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
int W, H;
pair<int, int> start(-1,-1);
pair<int, int> goal;
void bfs() {
queue<pair<int,int>> q;
q.push(start);
while (!q.empty()) {
int currX = q.front().first;
int currY = q.front().second;
q.pop();
for (auto dir : dirs) {
int nx = currX + dir[0];
int ny = currY + dir[1];
while (nx >= 0 && ny >= 0 && nx < W && ny < H && grid[ny][nx] != '*') {
if (!::count[ny][nx]) {
::count[ny][nx] = ::count[currY][currX] + 1;
q.push(pair<int, int>(nx, ny));
}
nx += dir[0]; ny += dir[1];
}
}
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
char temp;
cin >> W >> H;
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
cin >> temp;
grid[i][j] = temp;
if (temp == 'C') {
if (start.first == -1) {
start.first = j; start.second = i;
}
else {
goal.first = j; goal.second = i;
}
}
}
}
bfs();
cout << ::count[goal.second][goal.first] - 1;
}
'software engineering > PS' 카테고리의 다른 글
N-Queens (0) | 2021.02.23 |
---|---|
boj 1504 (0) | 2021.02.10 |
boj 3197 (0) | 2021.01.22 |
0/1 Knapsack problem (0) | 2021.01.20 |
Stack을 활용한 Remove Adjacent Duplicates(연속된 중복 제거) 문제 (0) | 2020.12.27 |