[SWA] 10966. 물놀이를 가자

10966. 물놀이를 가자

땅과 물이 표시된 NxM 지도가 주어진다.

모든 땅에서 물까지의 최소 이동 칸 수를 구하고, 모든 값의 합을 구하는 문제이다.

문제 해결 전략

우선 문제해결을 위해 bfs를 사용할 것이다.

모든 물에 대하여 상하좌우를 탐색을 하는데, 만약 땅을 만난다면 해당 땅을 queue에 push 한다.

그리고 그 땅들에 대하여 bfs를 진행한다.

진행하는 과정에서 가려는 곳에 대하여 현재까지의 칸수 + 1과 가려는 곳까지 이미 정해진 칸수 를 비교하여 갱신해 준다.

구해진 값들을 더해 준다.

코드

#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
char arr[1001][1001];
int dist[1001][1001];
int xpos[4] = {-1,1,0,0};
int ypos[4] = {0,0,-1,1};
int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
     
    int test_case;
    int T;
    cin>>T;
    for(test_case = 1; test_case <= T; ++test_case)
    {   
        int n,m;
        cin >> n >> m;
         
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                dist[i][j] = 0;
        }
         
        vector<pair<int,int>> v;
        queue<pair<int,int>> q;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                cin >> arr[i][j];
                if(arr[i][j] == 'W')
                {
                    v.push_back(make_pair(i,j));
                }
            }
        }
         
        for(int i=0;i<v.size();i++)
        {
            for(int j=0;j<4;j++)
            {
                int nx = xpos[j] + v[i].first;
                int ny = ypos[j] + v[i].second;
                if(nx < 0 || nx >= n || ny<0 || ny >= m)
                    continue;
                 
                if(arr[nx][ny] == 'L')
                {
                    if(dist[nx][ny] == 0){
                        dist[nx][ny] = 1;
                        q.push(make_pair(nx,ny));
                    }
                }
            }
        }
         
        while(!q.empty())
        {
            int x,y;
            x = q.front().first;
            y = q.front().second;
            q.pop();
             
            for(int i=0;i<4;i++)
            {
                int nx = xpos[i] + x;
                int ny = ypos[i] + y;
                if(nx < 0 || nx >= n || ny<0 || ny >= m)
                    continue;
                 
                if(arr[nx][ny] == 'W')
                    continue;
                 
                if(dist[nx][ny] == 0)
                {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push(make_pair(nx,ny));
                }
                else
                {
                    if(dist[nx][ny] > dist[x][y] + 1)
                    {
                        dist[nx][ny] = dist[x][y] + 1;
                        q.push(make_pair(nx,ny));
                    }
                    else
                        continue;                      
                }
            }
        }
         
        int cnt = 0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(arr[i][j] == 'L')
                    cnt += dist[i][j];
                else
                    continue;
            }
        }
         
        cout << "#" << test_case << " " << cnt << "\n";       
    }
    return 0;
}

출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXWXMZta-PsDFAST