#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int map[110][110];
int peopleNum;
int relation;
int Min = 9999999;
int ans;
 
queue<int> q;
int visited[110];
 
void init()
{
    for(int i = 1; i <= peopleNum; i++)
    {
        visited[i] = 0;
    }
}
 
void BFS(int start)
{
    visited[start] = 1;
    q.push(start);
    
    while(!q.empty())
    {
        start = q.front();
        q.pop();
        
        for(int i = 1; i <= peopleNum; i++)
        {
            if(map[start][i] == 1 && visited[i] == 0)
            {
                visited[i] = visited[start] + 1;
                q.push(i);
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1389_input.txt", "r", stdin);
    
    scanf("%d %d", &peopleNum, &relation);
    
    for(int i = 1; i <= relation; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        
        map[a][b] = 1;
        map[b][a] = 1;
    }
    
    for(int i = 1; i <= peopleNum; i++)
    {
        init();
        
        BFS(i);
        
        int sum = 0;
        for(int j = 1; j <= peopleNum; j++)
        {
            if(i == j)
            {
                continue;
            }
            else
            {
                sum += (visited[j]-1);
            }
        }
                
        if(sum < Min)
        {
            Min = sum;
            ans = i;
        }
    }
 
    cout << ans;
    
    return 0;
}
cs
저작자표시

'Baekjoon > BFS' 카테고리의 다른 글

[백준 16234] 인구이동 (BFS) (C/C++) (★★)  (0) 2019.12.07
[백준 2573] 빙산 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 1261] 알고스팟 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 14395] 4연산 (BFS) (C/C++)  (0) 2019.12.06
[백준 7576] 토마토 (BFS) (C/C++)  (0) 2019.12.06
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int crash;
}node;
 
int map[110][110];
int row, col;
int Min = 9999999;
 
queue<node> q;
int visited[110][110][210];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS()
{
    visited[0][0][0] = 1;
    q.push({0, 0, 0});
    
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int crash = q.front().crash;
        q.pop();
        
        if(x == row-1 && y == col-1)
        {
            if(crash < Min)
            {
                Min = crash;
            }
        }
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 0 && visited[xpos][ypos][crash] == 0 && crash <= row+col-2)
            {
                visited[xpos][ypos][crash] = 1;
                q.push({xpos, ypos, crash});
            }
            else if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 1 && visited[xpos][ypos][crash+1] == 0 && crash+1 <= row+col-2)
            {
                visited[xpos][ypos][crash+1] = 1;
                q.push({xpos, ypos, crash+1});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1261_input.txt", "r", stdin);
    
    scanf("%d %d", &col, &row);
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            scanf("%1d", &map[i][j]);
        }
    }
    
    BFS();
    
    printf("%d", Min);
        
    return 0;
}
cs
저작자표시

'Baekjoon > BFS' 카테고리의 다른 글

[백준 2573] 빙산 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 1389] 케빈 베이컨의 6단계 법칙 (BFS) (C/C++)  (0) 2019.12.06
[백준 14395] 4연산 (BFS) (C/C++)  (0) 2019.12.06
[백준 7576] 토마토 (BFS) (C/C++)  (0) 2019.12.06
[백준 5427] 불 (BFS) (C/C++) (★)  (0) 2019.12.05
#include <stdio.h>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
long long startNum, endNum;
string ans;
bool flag = false;
 
queue<pair<long long, string>> q;
map<long long, int> visited;
 
void BFS()
{
    visited[startNum] = 1;
    q.push({startNum, ""});
    
    while(!q.empty())
    {
        long long num = q.front().first;
        string oper = q.front().second;
        q.pop();
        
        if(num == endNum)
        {
            flag = true;
            ans = oper;
            
            return;
        }
        
        for(int i = 1; i <= 4; i++)
        {
            long long numTemp = num;
            
            // *
            if(i == 1)
            {
                numTemp *= numTemp;
                
                if(visited[numTemp] == 0)
                {
                    visited[numTemp] = 1;
                    q.push({numTemp, oper+"*"});
                }
            }
            // +
            else if(i == 2)
            {
                numTemp += numTemp;
                
                if(visited[numTemp] == 0)
                {
                    visited[numTemp] = 1;
                    q.push({numTemp, oper+"+"});
                }
            }
            // -
            else if(i == 3)
            {
                numTemp -= numTemp;
                
                if(visited[numTemp] == 0)
                {
                    visited[numTemp] = 1;
                    q.push({numTemp, oper+"-"});
                }
            }
            // /
            else if(i == 4)
            {
                if(numTemp == 0)
                {
                    continue;
                }
                
                numTemp /= numTemp;
                
                if(visited[numTemp] == 0)
                {
                    visited[numTemp] = 1;
                    q.push({numTemp, oper+"/"});
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B14395_input.txt", "r", stdin);
    
    cin >> startNum >> endNum;
    
    if(startNum == endNum)
    {
        cout << "0" << endl;
        
        return 0;
    }
    
    BFS();
    
    if(flag == true)
    {
        cout << ans << endl;
    }
    else
    {
        cout << "-1" << endl;
    }
    
    return 0;
}
cs
저작자표시

'Baekjoon > BFS' 카테고리의 다른 글

[백준 1389] 케빈 베이컨의 6단계 법칙 (BFS) (C/C++)  (0) 2019.12.06
[백준 1261] 알고스팟 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 7576] 토마토 (BFS) (C/C++)  (0) 2019.12.06
[백준 5427] 불 (BFS) (C/C++) (★)  (0) 2019.12.05
[백준 3055] 탈출 (BFS) (C/C++) (★)  (0) 2019.12.05
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int map[1010][1010];
int row, col;
int time;
 
queue<pair<int, int>> q;
int visited[1010][1010];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && x < row && y >= 0 && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
void tomato()
{
    int cnt = q.size();
    
    while(cnt--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && visited[xpos][ypos] == 0 && map[xpos][ypos] == 0)
            {
                map[xpos][ypos] = 1;
                
                visited[xpos][ypos] = visited[x][y] + 1;
                q.push({xpos, ypos});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B7576_input.txt", "r", stdin);
    
    cin >> col >> row;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
            
            if(map[i][j] == 1)
            {
                visited[i][j] = 1;
                q.push({i, j});
            }
        }
    }
    
    while(1)
    {
        if(check() == 1)
        {
            cout << time;
            break;
        }
        
        if(q.empty())
        {
            cout << "-1";
            break;
        }
        
        tomato();
        
        time++;
    }
    
    return 0;
}
cs
저작자표시

'Baekjoon > BFS' 카테고리의 다른 글

[백준 1261] 알고스팟 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 14395] 4연산 (BFS) (C/C++)  (0) 2019.12.06
[백준 5427] 불 (BFS) (C/C++) (★)  (0) 2019.12.05
[백준 3055] 탈출 (BFS) (C/C++) (★)  (0) 2019.12.05
[백준 2234] 성곽 (BFS) (C/C++) (★★)  (0) 2019.12.05
 
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
char map[1010][1010];
int row, col;
int T;
int endX, endY;
bool flag = false;
 
queue<pair<int, int>> s;
int visiteds[1010][1010];
 
queue<pair<int, int>> f;
int visitedf[1010][1010];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
void init()
{
    // swap을 통한 queue 비우기 -> pop 반복을 통해서도 가능 
    queue<pair<int, int>> empty1;
    swap(s, empty1);
    
    queue<pair<int, int>> empty2;
    swap(f, empty2);
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            visiteds[i][j] = 0;
            visitedf[i][j] = 0;
        }
    }
}
 
int safe(int x, int y)
{
    if(x >= 0 && x < row && y >= 0 && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void fire()
{
    int cnt = f.size();
    
    while(cnt--)
    {
        int x = f.front().first;
        int y = f.front().second;
        f.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && visitedf[xpos][ypos] == 0 && map[xpos][ypos] != '#')
            {
                map[xpos][ypos] = '*';
                
                visitedf[xpos][ypos] = 1;
                f.push({xpos, ypos});
            }
        }    
    }
}
 
void sang()
{
    int cnt = s.size();
    
    while(cnt--)
    {
        int x = s.front().first;
        int y = s.front().second;
        s.pop();
        
        if(x == 0 || y == 0 || x == row-1 || y == col-1)
        {
            flag = true;
            endX = x;
            endY = y;
            
            return;
        }
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && visiteds[xpos][ypos] == 0 && map[xpos][ypos] == '.')
            {
                visiteds[xpos][ypos] = visiteds[x][y] + 1;
                s.push({xpos, ypos});
            }
        }    
    }
}
 
int main(void)
{
//    freopen("B5427_input.txt", "r", stdin);
    
    cin >> T;
    
    for(int n = 1; n <= T; n++)
    {
        flag = false;
        
        cin >> col >> row;
        
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                cin >> map[i][j];
                
                if(map[i][j] == '*')
                {
                    visitedf[i][j] = 1;
                    f.push({i, j});
                }
                else if(map[i][j] == '@')
                {
                    visiteds[i][j] = 1;
                    s.push({i, j});
                }
            }
        }
        
        int time = 0;
        while(1)
        {
            if(flag == true)
            {
                cout << visiteds[endX][endY] << endl;
                break;
            }
            
            if(s.empty())
            {
                cout << "IMPOSSIBLE" << endl;
                break;
            }
            
            fire();
            sang();
        }
 
        init();
    }
        
    return 0;
}
cs
저작자표시

'Baekjoon > BFS' 카테고리의 다른 글

[백준 14395] 4연산 (BFS) (C/C++)  (0) 2019.12.06
[백준 7576] 토마토 (BFS) (C/C++)  (0) 2019.12.06
[백준 3055] 탈출 (BFS) (C/C++) (★)  (0) 2019.12.05
[백준 2234] 성곽 (BFS) (C/C++) (★★)  (0) 2019.12.05
[백준 12886] 돌 그룹 (BFS) (C/C++) (★)  (0) 2019.12.05
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
char map[55][55];
int row, col;
int endX, endY;
int time;
 
queue<pair<int, int>> h;
int visitedh[55][55];
 
queue<pair<int, int>> w;
int visitedw[55][55];
 
int dx[4] = {-1, 1, 0 ,0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && x < row && y >= 0 && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void water()
{
    // 한턴만 BFS 수행하기 위해서 size만큼 고정 
    int cnt = w.size();
    
    while(cnt--)
    {
        int x = w.front().first;
        int y = w.front().second;
        w.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            // 물이 참과 동시에 고슴도치도 이동하기 때문에 고슴도치가 현재 있는곳도 체크 
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 'X' && map[xpos][ypos] != 'D' && visitedw[xpos][ypos] == 0)
            {
                map[xpos][ypos] = '*';
                
                visitedw[xpos][ypos] = 1;
                w.push({xpos, ypos});
            }
        }
    }
}
 
void hedgehog()
{
    // 한턴만 BFS 수행하기 위해서 size만큼 고정 
    int cnt = h.size();
    
    while(cnt--)
    {
        int x = h.front().first;
        int y = h.front().second;
        h.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && (map[xpos][ypos] == '.' || map[xpos][ypos] == 'D') && visitedh[xpos][ypos] == 0)
            {
                visitedh[xpos][ypos] = 1;
                h.push({xpos, ypos});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B3055_input.txt", "r", stdin);
    
    scanf("%d %d", &row, &col);
 
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
            
            if(map[i][j] == '*')
            {
                visitedw[i][j] = 1;
                w.push({i, j});
            }
            else if(map[i][j] == 'S')
            {
                visitedh[i][j] = 1;
                h.push({i, j});
            }
            else if(map[i][j] == 'D')
            {
                endX = i;
                endY = j;
            }
        }
    }
    
    while(1)
    {    
        if(visitedh[endX][endY] == 1)
        {
            cout << time << endl;
            return 0;
        }
        
        if(h.empty())
        {
            cout << "KAKTUS" << endl;
            return 0;
        }
        
        water();
        hedgehog();
        
        time++;
    }
        
    return 0;
}
cs
저작자표시

'Baekjoon > BFS' 카테고리의 다른 글

[백준 7576] 토마토 (BFS) (C/C++)  (0) 2019.12.06
[백준 5427] 불 (BFS) (C/C++) (★)  (0) 2019.12.05
[백준 2234] 성곽 (BFS) (C/C++) (★★)  (0) 2019.12.05
[백준 12886] 돌 그룹 (BFS) (C/C++) (★)  (0) 2019.12.05
[백준 14442] 벽 부수고 이동하기2 (BFS) (C/C++) (★)  (0) 2019.12.04
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int map[55][55];
int mapCopy[55][55];
int row, col;
int color;
int roomCnt;
int roomMax = 1;
int crashMax;
int roomArea[2510];
 
queue<pair<int, int>> q;
int visited[55][55];
 
int dx[4] = {0, -1, 0, 1}; // 서 북 동 남 
int dy[4] = {-1, 0, 1, 0}; // 서 북 동 남
 
int safe(int x, int y)
{
    if(x >= 0 && x < row && y >= 0 && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS(int x, int y, int color)
{
    int areaCnt = 1;
    mapCopy[x][y] = color;
    
    visited[x][y] = 1;
    q.push({x, y});
    
    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
//            if((map[x][y] & (1 << i)) != 0)
//            {
//                continue;
//            } 
            
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && visited[xpos][ypos] == 0 && (map[x][y] & (1 << i)) == 0)
            {
                visited[xpos][ypos] = 1;
                q.push({xpos, ypos});
                
                mapCopy[xpos][ypos] = color;
                areaCnt++;
                
                if(roomMax < areaCnt)
                {
                    roomMax = areaCnt;
                }
            }
        }
    }
    
    roomArea[++roomCnt] = areaCnt;
}
 
void crash_wall()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            for(int k = 0; k < 4; k++)
            {
                int x = i+dx[k];
                int y = j+dy[k];
                
                if(safe(x, y) == 1 && mapCopy[i][j] != mapCopy[x][y])
                {
                    if(crashMax < roomArea[mapCopy[i][j]] + roomArea[mapCopy[x][y]])
                    {
                        crashMax = roomArea[mapCopy[i][j]] + roomArea[mapCopy[x][y]];
                    }
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2234_input.txt", "r", stdin);
    
    cin >> col >> row;
 
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
        }
    }
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(visited[i][j] == 0)
            {
                ++color;
                BFS(i, j, color);
            }
        }
    }
    
    crash_wall();
    
    cout << roomCnt << endl;
    cout << roomMax << endl;
    cout << crashMax << endl;
 
    return 0;
}
cs
저작자표시

'Baekjoon > BFS' 카테고리의 다른 글

[백준 5427] 불 (BFS) (C/C++) (★)  (0) 2019.12.05
[백준 3055] 탈출 (BFS) (C/C++) (★)  (0) 2019.12.05
[백준 12886] 돌 그룹 (BFS) (C/C++) (★)  (0) 2019.12.05
[백준 14442] 벽 부수고 이동하기2 (BFS) (C/C++) (★)  (0) 2019.12.04
[백준 2206] 벽 부수고 이동하기 (BFS) (C/C++)  (0) 2019.12.04
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
typedef struct node
{
    int A;
    int B;
    int C;    
}node;
 
int A, B, C;
bool flag = false;
 
queue<node> q;
set<pair<pair<int, int>, int>> visited;
 
void BFS()
{
    visited.insert({{A, B}, C});
    q.push({A, B, C});
    
    while(!q.empty())
    {
        int A = q.front().A;
        int B = q.front().B;
        int C = q.front().C;
        q.pop();
        
        if(A == B && B == C)
        {
            flag = true;
            return;
        }
        
        // 3C2 = 3
        for(int i = 1; i <= 3; i++)
        {
            // A-B
            if(i == 1)
            {
                if(A > B)
                {
                    if(visited.find({{A-B, B+B}, C}) == visited.end())
                    {
                        visited.insert({{A-B, B+B}, C});    
                        q.push({A-B, B+B, C});    
                    }
                }
                else
                {
                    if(visited.find({{A+A, B-A}, C}) == visited.end())
                    {
                        visited.insert({{A+A, B-A}, C});    
                        q.push({A+A, B-A, C});    
                    }
                }
            }
            // B-C
            else if(i == 2)
            {
                if(B > C)
                {
                    if(visited.find({{A, B-C}, C+C}) == visited.end())
                    {
                        visited.insert({{A, B-C}, C+C});    
                        q.push({A, B-C, C+C});    
                    }
                }
                else
                {
                    if(visited.find({{A, B+B}, C-B}) == visited.end())
                    {
                        visited.insert({{A, B+B}, C-B});
                        q.push({A, B+B, C-B});    
                    }
                }
            }
            // A-C
            else if(i == 3)
            {
                if(A > C)
                {
                    if(visited.find({{A-C, B}, C+C}) == visited.end())
                    {
                        visited.insert({{A-C, B}, C+C});
                        q.push({A-C, B, C+C});    
                    }
                }
                else
                {
                    if(visited.find({{A+A, B}, C-A}) == visited.end())
                    {
                        visited.insert({{A+A, B}, C-A});    
                        q.push({A+A, B, C-A});    
                    }
                }
            }    
        }
    }
}
 
int main(void)
{
//    freopen("B12886_input.txt", "r", stdin);
    
    scanf("%d %d %d", &A, &B, &C);
    
    BFS();
    
    if(flag == true)
    {
        printf("1");
    }
    else
    {
        printf("0");
    }
        
    return 0;
}
cs
저작자표시

'Baekjoon > BFS' 카테고리의 다른 글

[백준 3055] 탈출 (BFS) (C/C++) (★)  (0) 2019.12.05
[백준 2234] 성곽 (BFS) (C/C++) (★★)  (0) 2019.12.05
[백준 14442] 벽 부수고 이동하기2 (BFS) (C/C++) (★)  (0) 2019.12.04
[백준 2206] 벽 부수고 이동하기 (BFS) (C/C++)  (0) 2019.12.04
[백준 11724] 연결요소의 개수 (BFS) (C/C++)  (0) 2019.12.04

+ Recent posts

티스토리툴바