[백준] 16441 아기돼지와 늑대

최적화란 무엇일까..

BFS로 풀면 되는 문제이다.. 나만 시간이 꼴찌다.. 슬프다..

BFS로 하면 되는데 생각해야할 부분은 빙판에서 미끄러질 때다

첨에는 그냥 빙판에서 미끄러질때 똑같이 check하고 풀었는데 그럼

빙판을 4방향에서 전부 미끄러지는 경우를 생각하면 예외가 나올 수 있다

그래서 빙판미끄러지는 경우를 그냥 하나하나 다 코딩해버려따 

헷갈릴 때는 우선 하고 생각하자..!!

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
int n,m;
char arr[111][111];
vector<pair<int,int>> wvt;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
bool check[111][111];
bool unsafe[111][111];
 
bool inner(int x,int y){
    return (0<= x && x<n && 0<=y && y<m);
}
 
void bfs(int _x,int _y){
    memset(check,0,sizeof(check));
    queue<pair<int,int>> q;
    q.push({_x,_y});
    check[_x][_y]=true;
    unsafe[_x][_y]=true;
 
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        check[x][y]=true;
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(inner(nx,ny)){
                if(arr[nx][ny]=='.' && !check[nx][ny]){
                    check[nx][ny]=true;
                    unsafe[nx][ny]=true;
                    q.push({nx,ny});
                } else if(arr[nx][ny]=='+'){
                    while(inner(nx,ny)){
                        if(arr[nx][ny] =='.' && !check[nx][ny]){
                            check[nx][ny]=true;
                            unsafe[nx][ny]=true;
                            q.push({nx,ny});
                            break;
                        } else if(arr[nx][ny]=='#'){
                            check[nx-dx[i]][ny-dy[i]] =true;
                            q.push({nx-dx[i],ny-dy[i]});
                            break;
                        } else if(arr[nx][ny]=='+' && !check[nx][ny]){
                            nx+=dx[i]; ny+=dy[i];
                        } else break;
                    }
                }
            }
        }
    }
}
 
 
int main(){
    //freopen("input.txt","r",stdin);
    scanf(" %d %d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf(" %1c",&arr[i][j]);
            if(arr[i][j]=='W') wvt.push_back({i,j});
        }
    }
    for(int i=0;i<wvt.size();i++) bfs(wvt[i].first,wvt[i].second);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j]=='.' && !unsafe[i][j]) printf("P");
            else printf("%c",arr[i][j]);
        }
        puts("");
    }
}