백준 6087

처음에 쉽게 풀거라 생각하고 덤볐다가 또 고전했다...

이 문제 또한 bfs를 이용해서 풀었다.

문제를 간단히 하자면, 간단하게도 방향 전환이 될 때, 방향 전환된 수의 최솟값을 통해 목적지까지 도달하는 문제이다.

코드를 먼저 보자.

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

struct pos{
    int x, y, dir, val;
}typedef pos;

int w, h;
char a[101][101];
int change[101][101];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
vector<pos> v;

bool isPossible(pos p){
    if(p.x < 0 || p. y < 0 || p.x >= h || p.y >= w) return false;
    return true;
}

void bfs(){
    queue<pos> q;
    q.push(v[0]);
    while(!q.empty()){
        pos node = q.front(); q.pop();
        for(int i = 0; i < 4; i++){
            pos next = {node.x+dx[i], node.y+dy[i], i, node.val};
            if(isPossible(next) && !(next.x==v[0].x && next.y==v[0].y)){
                if(a[next.x][next.y] != '*'){
                    if(node.dir != next.dir) next.val += 1;

                    if(change[next.x][next.y] >= next.val || change[next.x][next.y] == -1){
                        change[next.x][next.y] = next.val;
                        q.push(next);
                    }
                }
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> w >> h;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            change[i][j] = -1;
            cin >> a[i][j];
            if(a[i][j] == 'C') {v.push_back({i,j, -1, -1});}
        }
    }
    bfs();
    cout << change[v[1].x][v[1].y];
}

struct pos에서 dir은 진행 방향, val은 지점까지 가는데 사용한 거울의 수이다.

그리고 C 좌표에서 처음 dir과 val을 -1로 받는 것은 이후 dir 차이가 발생했을 때 val값에 1을 더함으로 0값으로 초기값을 맞추기 위함이다.

change 배열은 해당 지점까지 가는데 사용한 최소 거울의 수이다.

 

bfs를 진행하는데, dir 값이 이전값(node의 dir값)과 다를 경우 val 값에 1을 더하며, 이를 change배열에 해당 좌표값에 위치한 값과 비교하여 더 작거나 같은 값으로 change 배열을 갱신해준다.

 

해당 문제는 풀기는 간단하게 금방 답 근처까지 갔으나, 하나 간과했던 것은 struct pos에 val 값을 추가하지 않고 change 배열값으로만 bfs를 진행하여 최소갑을 구해 값이 현재 node에 따른 값이 아닌 다른 node의 값으로 덧씌워져 bfs가 진행된다는 점이었다.

 

다음부턴 정신 차리고 풀자..