백준 바킹독 BFS 모음 - 1926 그림, 2178 미로탐색, 7576 토마토, 4179 불!

1926번 그림 

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int visited[502][502];
int table[502][502];
int maxval = -1;
int xcor[4] = { -1, 0, 1, 0};
int ycor[4] = {0, 1, 0, -1};
int main()
{
    int n ,m;
    
    cin>>n>>m;
    for(int i = 0; i < n ; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin>>table[i][j];
        }
    }
    int numpic =0;
    for(int i = 0; i < n ; i++)
    {
        for (int j = 0; j < m; j++)
        {
            queue <pair<int,int>> q;
            if (table[i][j] == 1 && visited[i][j] != 1)
            {
                int pic_cnt = 1;
                q.push(make_pair(i, j));
                visited[i][j] = 1;
                while(!q.empty())
                {
                    pair <int, int> cur = q.front();
                    q.pop();
                    for (int i = 0; i < 4; i++)
                    {
                        int curX = cur.first + xcor[i];
                        int curY = cur.second + ycor[i];
                        if (curX < 0 || curX >=n || curY < 0 || curY >= m) continue;
                        if (visited[curX][curY] == 1 || table[curX][curY] == 0) continue;
                        q.push(make_pair(curX, curY));
                        visited[curX][curY] = 1;
                        pic_cnt++;
                    }
                }
                if ( pic_cnt > maxval)
                    maxval = pic_cnt;
                numpic++;
            }
        }
    }
    if (maxval == -1) maxval = 0;
    cout<< numpic << '\n' << maxval << '\n';
    return 0;
}

기본 BFS 문제

 

2178 미로탐색 

 

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int table[102][102];
int visited[102][102];
queue<pair<int,int>>q;
int dirx[4] = {0, -1, 0 , 1};
int diry[4] = {1, 0, -1, 0};

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 0; i< n; i++)
    {
        string tmp;
        cin>>tmp;
        for(int j = 0; j < m ; j++)
        {
            table[i][j] = tmp[j] - '0';
        }
    }
    q.push(make_pair(0,0));
    visited[0][0] = 1;
    while(!q.empty())
    {
        pair<int,int> cur = q.front(); q.pop();
        for(int i = 0; i <4; i++)
        {
            int newX = cur.first + dirx[i];
            int newY = cur.second + diry[i];
            if (table[newX][newY] == 0 || visited[newX][newY] >= 1) continue;
            if (newX < 0 || newX >= n || newY < 0 || newY >= m) continue;
            visited[newX][newY] = visited[cur.first][cur.second] + 1;
            q.push(make_pair(newX, newY));
        }
    }
    cout<<visited[n-1][m-1];
    return 0;
}

다 똑같은 문제들인데 이 문제의 경우 visited 배열에 현재까지 이동한 숫자를 증가시켜가며 넣어준다.

 

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int table[1002][1002];
int visited[1002][1002];
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};
queue<pair<int,int>>q;

int main()
{
    int n, m;
    
    cin>>m>>n;
    for(int i = 0; i< n; i++)
    {
        for(int j = 0; j< m; j++)
        {
            cin>>table[i][j];
            if (table[i][j] == 1){
                q.push(make_pair(i,j));
            }
            if (table[i][j] == 0)
                visited[i][j] = -1;
        }
    }
    while (!q.empty())
    {
        pair<int,int> cur = q.front(); q.pop();
        for(int i = 0; i < 4; i++)
        {
            int newX = cur.first + dirx[i];
            int newY = cur.second + diry[i];
            if (newX < 0 || newX >= n || newY < 0 || newY >= m) continue;
          //  if (table[newX][newY] == 1 || table[newX][newY] == -1) continue;
            if (visited[newX][newY] >= 0) continue;
            visited[newX][newY] = visited[cur.first][cur.second]+1;
            q.push(make_pair(newX, newY));
        }
    }
    int maxval = 0;
    for(int i =0; i< n; i++)
    {
        for(int j =0; j <m ;j++)
        {
            if(visited[i][j] == -1)
            {
                cout<< -1;
                return 0;
            }
            maxval = max(maxval, visited[i][j]);
        }
    }
  cout<<maxval<<'\n';
    //return 0;
    
   // return (0);
}

불!

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;


queue<pair<int, int>> qfire;
queue<pair<int, int>> qhuman;
int xdir[4] = {-1, 0, 1, 0};
int ydir[4] = {0, 1, 0, -1};
int fdist[1002][1002];
int hdist[1002][1002];

int table[1002][1002];
int main()
{
    //불, 지훈이 각각에 대해 bfs 를 돌리는데, 불먼저 돌려서 그 dist 값을 배열하나에 저장
    //이후 지훈이가 갈수있는걸 bfs로 진행하면서 불이 먼저 도달한 경우에는 못가니까 continue
    int r, c;
    cin>>r>>c;
    for(int i = 0; i < r; i++)
    {
        string tmp;
        cin>>tmp;
        for(int j = 0; j < c; j++)
        {
            table[i][j] = tmp[j];
            fdist[i][j] = -1;
            hdist[i][j] = -1;
            if(tmp[j] == 'F')
            {
                qfire.push(make_pair(i,j));
                fdist[i][j] = 0;
            }
            if(tmp[j] == 'J')
            {
                qhuman.push(make_pair(i,j));
                hdist[i][j] = 0;
            }
        }
    }
    while (!qfire.empty())
    {
        auto cur = qfire.front();
        qfire.pop();
        for(int i =0; i< 4; i++)
        {
            int curX = cur.first + xdir[i];
            int curY = cur.second + ydir[i];
            if (curX < 0 || curX >= r || curY < 0 || curY >= c) continue;
            if (fdist[curX][curY] >= 0) continue;
            if (table[curX][curY] == '#') continue;
            fdist[curX][curY] = fdist[cur.first][cur.second] + 1;
            qfire.push(make_pair(curX, curY));
        }
    }
    
    while(!qhuman.empty())
    {
        auto cur = qhuman.front();
        qhuman.pop();
        for(int i =0; i<4; i++)
        {
            int curX = cur.first + xdir[i];
            int curY = cur.second + ydir[i];
            if (curX < 0 || curX >= r || curY < 0 || curY >= c)
            {
                cout<<hdist[cur.first][cur.second] + 1<< '\n';
                return 0;
            }
            if (hdist[curX][curY] >= 0)
                continue;
            if (table[curX][curY] == '#')
                continue;
            if (hdist[cur.first][cur.second] + 1 >= fdist[curX][curY] && fdist[curX][curY] != -1)
                continue;
        
            hdist[curX][curY] = hdist[cur.first][cur.second] + 1;
            qhuman.push(make_pair(curX, curY));
        }
    }
    int ans = 0;
    for (int i = 0; i< c; i++)
    {
        if (hdist[0][i] != 0)
            ans = max(ans, hdist[0][i]);
        if (hdist[r-1][i] != 0)
            ans = max(ans,hdist[r-1][i]);
    }
    for (int i = 0; i < r; i++)
    {
        if (hdist[i][0] != 0)
            ans = max(ans, hdist[i][0]);
        if (hdist[i][c-1] != 0)
            ans = max(ans, hdist[i][c-1]);
    }

    if (ans ==0 )
    {
        cout<<"IMPOSSIBLE\n";
        return 0;
    }
    cout<<ans<<'\n';
    return 0;
}