[bfs] 백준 16569 화산쇄설류

https://www.acmicpc.net/problem/16569

생각보다 많이 힘들었습니다. 

화산재에 덮이는 시간을 저장하는 배열을 하나 더 만들어서 풀었습니다.

처음에 화산의 위치를 재상이가 지나갈 수 있게 만들어서 틀렸었습니다.

그래서 40번 줄을 수정해서 화산이 있는 곳의 시간은 0으로 저장하니 맞았습니다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    int m,n,v,u_x,u_y;
    int map[100][100];
    int t_map[100][100];        //화산재에 덮이는 시간
    pair<int,pair<int,int>> p[10000];
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
    
    for(int i = 0; i < 100; i++){
        for(int j = 0; j < 100; j++)
            t_map[i][j] =10000;
    }
    
    cin >> m >> n >> v >> u_x >> u_y;
    
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++)
            cin >> map[i][j];
    }
    
    for(int i = 0; i < v; i++){
        cin >> p[i].second.first >> p[i].second.second >> p[i].first ;
    }
 
    //화산재에 덮이는 시간들 저장.
    
    for(int i = 0; i < v; i++){
        
        bool visited[100][100] = {0};
        queue<pair<int,int>> q;
        int t = p[i].first+1;
        
        q.push({p[i].second.second-1, p[i].second.first-1});
        t_map[q.front().second][q.front().first] = 0;
        while(!q.empty()){
            int size = q.size();
            
            for(int k = 0; k < size; k++){
                int x = q.front().first; int y = q.front().second;
                q.pop();
                
                for(int j = 0; j < 4; j++){
                    int tx = x+dx[j]; int ty= y+dy[j];
                    if(visited[ty][tx]) continue;
                    if(ty >= m || tx >= n || ty < 0 || tx < 0) continue;
                    t_map[ty][tx] = min(t_map[ty][tx],t);
                    visited[ty][tx] = true;
                    q.push({tx,ty});
                }
            }
            t+=1;
        }
    }
    
    
    int t = 1;
    int height,max_t = 0;
    bool visited[100][100] = {};
    queue<pair<int,int>> q;
    //처음 위치의 높이를 height에 저장.
    q.push({u_y-1,u_x-1});
    height = map[q.front().second][q.front().first];
    
    while(!q.empty()){
        int size = q.size();
 
        for(int i = 0; i < size; i++){
            int x = q.front().first; int y = q.front().second;
            q.pop();
            
            for(int j = 0; j < 4; j++){
                int tx = x+dx[j]; int ty = y+dy[j];
                
                if(visited[ty][tx]) continue;
                if(ty >= m || tx >= n || ty < 0 || tx < 0) continue;
                if(t_map[ty][tx] <= t){
                    visited[ty][tx] = 1;
                    continue;
                }
                if(height == map[ty][tx])
                    max_t = min(max_t,t);
                if(height < map[ty][tx]){
                    max_t = t;
                    height = map[ty][tx];
                }
                visited[ty][tx] = true;
                q.push({tx,ty});
            }
        }
        t+=1;
    }
    
    cout << height <<' ' << max_t;
}