#include <stdio.h>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
 
string startNum, endNum;
string digit = "0123456789"; // 자릿수 저장 
int T;
bool flag = false;
 
queue<string> q;
map<string, int> visited;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int check(string temp)
{
    int num = stoi(temp);
    
    for(int i = 2; i <= sqrt(num); i++)
    {
        if(num % i == 0)
        {
            return 0;
        }
    }
    
    return 1;
}
 
void BFS()
{
    visited[startNum] = 1;
    q.push(startNum);
    
    while(!q.empty())
    {
        string num = q.front();
        q.pop();
        
        if(num == endNum)
        {
            flag = true;
            return;
        }
        
        // 4 자리수 
        for(int i = 0; i < 4; i++)
        {
            string temp = num;
            
            // 첫째자리수 
            if(i == 0)
            {
                // 각 자리수 1~9 
                for(int j = 1; j <= 9; j++)
                {
                    // 교환 
                    temp[i] = digit[j];
                    
                    if(visited[temp] == 0 && check(temp) == 1)
                    {
                        visited[temp] = visited[num]+1;
                        q.push(temp);
                    }
                }
            }
            else
            {
                // 각 자리수 0~9 
                for(int j = 0; j <= 9; j++)
                {
                    // 교환
                    temp[i] = digit[j];
                    
                    if(visited[temp] == 0 && check(temp) == 1)
                    {
                        visited[temp] = visited[num]+1;
                        q.push(temp);
                    }
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1963_input.txt", "r", stdin);
    
    cin >> T;
    
    for(int n = 1; n <= T; n++)
    {
        queue<string> empty;
        swap(empty, q);
        visited.clear();
        flag = false;
        
        cin >> startNum >> endNum;        
        
        BFS();
        
        if(flag == false)
        {
            cout << "Impossible" << endl;
        }
        else
        {
            cout << visited[endNum]-1 << endl;
        }    
    }
    
    return 0;
}
cs
저작자표시

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

[백준 1707] 이분 그래프 (BFS) (C/C++) (★)  (0) 2020.01.26
[백준 1525] 퍼즐 (BFS) (C/C++) (★★)  (0) 2019.12.13
[백준 16236] 아기상어 (BFS) (C/C++) (★★★★)  (0) 2019.12.13
[백준 1194] 달이 차오른다, 가자. (BFS, Bitmask) (C/C++) (★★★)  (0) 2019.12.11
[백준 3197] 백조의 호수 (BFS) (C/C++) (★★★)  (0) 2019.12.09
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int size;
    int eat;
    int dist;
}node;
 
int map[21][21];
int N;
int ans;
 
queue<node> q;
int visited[21][21];
 
node f;
vector<node> fish;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
bool cmp(node A, node B)
{
    // 거리가 같을 경우
    if(A.dist == B.dist)
    {
        // 위쪽에 있는 먹이가 여러개인 경우
        if(A.x == B.x)
        {
            // 왼쪽에 있는 먹이
            if(A.y < B.y)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        // 위쪽에 있는 먹이 
        else if(A.x < B.x)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    // 가장 짧은 거리 
    else if(A.dist < B.dist)
    {
        return true;
    }
    else
    {
        return false;
    }
}
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS()
{
    while(1)
    {
        memset(visited, 0, sizeof(visited));
        fish.clear();
        
        visited[f.x][f.y] = 1;
        q.push(f);
        
        // 먹이가 될수있는 물고기를 찾는 반복문 
        while(!q.empty())
        {
            int x = q.front().x;
            int y = q.front().y;
            int size = q.front().size;
            int eat = q.front().eat;
            int dist = q.front().dist;
            q.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] == 0 || map[xpos][ypos] == 9 || map[xpos][ypos] == size) && visited[xpos][ypos] == 0)
                {
                    visited[xpos][ypos] = 1;
                    q.push({xpos, ypos, size, eat, dist+1});
                }
                // 먹이가 있는 경우 
                else if(safe(xpos, ypos) == 1 && map[xpos][ypos] < size && visited[xpos][ypos] == 0)
                {
                    visited[xpos][ypos] = 1;
                    q.push({xpos, ypos, size, eat, dist+1});
                    
                    // 먹이가 될수 있는 물고기 저장 
                    fish.push_back({xpos, ypos, size, eat, dist+1});
                }
            }
        }
        
        // 먹이가 될 수 있는 물고기가 없으면 종료 
        if(fish.size() == 0)
        {
            return;
        }
        
        sort(fish.begin(), fish.end(), cmp);
        
        // 물고기를 잡아먹음 
        fish[0].eat++;
        
        // 상어의 크기 = 잡아먹은 물고기 수  
        if(fish[0].size == fish[0].eat)
        {
            fish[0].size++;
            fish[0].eat = 0;
        }
        
        // 잡아 먹은 물고기 지움
        map[fish[0].x][fish[0].y] = 0;
        
        // 움직인 거리 저장
        ans += fish[0].dist;
        
        // f 초기화
        f = {fish[0].x, fish[0].y, fish[0].size, fish[0].eat, 0}; 
    }
}
 
int main(void)
{
//    freopen("B16236_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin >> map[i][j];    
            
            if(map[i][j] == 9)
            {
                f = {i, j, 2, 0, 0};
            }
        }
    }
    
    BFS();
    
    cout << ans; 
 
    return 0;
}
cs
저작자표시

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

[백준 1525] 퍼즐 (BFS) (C/C++) (★★)  (0) 2019.12.13
[백준 1963] 소수경로 (BFS) (C/C++)  (0) 2019.12.13
[백준 1194] 달이 차오른다, 가자. (BFS, Bitmask) (C/C++) (★★★)  (0) 2019.12.11
[백준 3197] 백조의 호수 (BFS) (C/C++) (★★★)  (0) 2019.12.09
[백준 9019] DSLR (BFS) (C/C++)  (0) 2019.12.08
#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 key; // 가지고 있는 키의 합 
    int cnt;
}node;
 
char map[55][55];
int row, col;
int startX, startY;
int ans = -1;
 
queue<node> q;
int visited[55][55][64]; // 비트연산 사용 A(1), B(2), C(4), D(8), E(16), F(32) -> 최대합 2^6-1 이기때문에 64만큼의 배열 선언 
 
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 BFS()
{
    visited[startX][startY][0] = 1;
    q.push({startX, startY, 0, 0});
    
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int key = q.front().key;
        int cnt = q.front().cnt;
        q.pop();
        
        if(map[x][y] == '1')
        {
            ans = cnt;
            return;
        }
        
        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] == '0' || map[xpos][ypos] == '1') && visited[xpos][ypos][key] == 0)
            {
                visited[xpos][ypos][key] = 1;
                q.push({xpos, ypos, key, cnt+1});    
            }
            // 열쇠를 찾음 
            else if(safe(xpos, ypos) == 1 && 'a' <= map[xpos][ypos] && map[xpos][ypos] <= 'f' && visited[xpos][ypos][key] == 0)
            {
                // 안 찾은 열쇠면 
                if((key & (1 << map[xpos][ypos] - 'a')) != (1 << map[xpos][ypos] - 'a'))
                {
                    int tempKey = key + (1 << (map[xpos][ypos] - 'a'));
                
                    visited[xpos][ypos][tempKey] = 1;
                    q.push({xpos, ypos, tempKey, cnt+1});    
                }
                // 찾은 열쇠면 
                else
                {
                    visited[xpos][ypos][key] = 1;
                    q.push({xpos, ypos, key, cnt+1});    
                }
            }
            // 문을 찾음 
            else if(safe(xpos, ypos) == 1 && 'A' <= map[xpos][ypos] && map[xpos][ypos] <= 'F' && visited[xpos][ypos][key] == 0)
            {
                // 문을 열 열쇠가 있는지 확인 
                if((key & (1 << map[xpos][ypos] - 'A')) == (1 << map[xpos][ypos] - 'A'))
                {    
                    visited[xpos][ypos][key] = 1;
                    q.push({xpos, ypos, key, cnt+1});
                }
            }
        }    
    }
}
 
int main(void)
{
//    freopen("B1194_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
            
            if(map[i][j] == '0')
            {
                startX = i;
                startY = j;
            }
        }
    }
    
    BFS();
    
    cout << ans;
        
    return 0;
}
cs
저작자표시

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

[백준 1963] 소수경로 (BFS) (C/C++)  (0) 2019.12.13
[백준 16236] 아기상어 (BFS) (C/C++) (★★★★)  (0) 2019.12.13
[백준 3197] 백조의 호수 (BFS) (C/C++) (★★★)  (0) 2019.12.09
[백준 9019] DSLR (BFS) (C/C++)  (0) 2019.12.08
[백준 11559] Puyo Puyo (BFS) (C/C++) (★)  (0) 2019.12.08
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
char map[1510][1510];
int row, col;
int swanX, swanY;
int day;
bool flag = false;
 
queue<pair<int, int>> m;
 
queue<pair<int, int>> reserve;
int visiteds[1510][1510];
 
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 melt()
{
    int cnt = m.size();
    
    while(cnt--)
    {
        int x = m.front().first;
        int y = m.front().second;
        m.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')
            {
                m.push({xpos, ypos});
                map[xpos][ypos] = '.';
            }
        }
    }
}
 
void swan()
{    
    queue<pair<int, int>> s;
    s = reserve;
    
    // <reserve queue> clear
    queue<pair<int, int>> empty;
    swap(empty, reserve);
    
    while(!s.empty())
    {
        int x = s.front().first;
        int y = s.front().second;
        s.pop();
        
        
        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] = 1;
                s.push({xpos, ypos});
            }
            else if(safe(xpos, ypos) == 1 && visiteds[xpos][ypos] == 0 && map[xpos][ypos] == 'L')
            {
                visiteds[xpos][ypos] = 1;
                s.push({xpos, ypos});
                
                flag = true;
                return;
            }
            // 상하좌우가 X면 백조가 더이상 못가기 때문에, 백조 위치 저장 
            else if(safe(xpos, ypos) == 1 && visiteds[xpos][ypos] == 0 && map[xpos][ypos] == 'X')
            {
                reserve.push({x, y});
            }
        }
    }
}
 
void print()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cout << map[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
 
int main(void)
{
//    freopen("B3197_input.txt", "r", stdin);
    
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
            
            // 백조도 물로 친다(중요) 
            if(map[i][j] == '.' || map[i][j] == 'L')
            {
                m.push({i, j});
            }
            
            if(map[i][j] == 'L')
            {
                swanX = i;
                swanY = j;
            }
        }
    }
    
    // 백조 초기 시작값 저장 
    reserve.push({swanX, swanY});
    visiteds[swanX][swanY] = 1;
 
    while(1)
    {
        day++;
        
        melt();
    
        swan();
        
//        print();
        
        if(flag == true)
        {
            cout << day << "\n";
            break;
        }    
    }
        
    return 0;
}
cs
저작자표시

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

[백준 16236] 아기상어 (BFS) (C/C++) (★★★★)  (0) 2019.12.13
[백준 1194] 달이 차오른다, 가자. (BFS, Bitmask) (C/C++) (★★★)  (0) 2019.12.11
[백준 9019] DSLR (BFS) (C/C++)  (0) 2019.12.08
[백준 11559] Puyo Puyo (BFS) (C/C++) (★)  (0) 2019.12.08
[백준 16234] 인구이동 (BFS) (C/C++) (★★)  (0) 2019.12.07
#include <stdio.h>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int A, B;
int T;
 
void BFS()
{
    queue<pair<int, string>> q;
    int visited[10010] = {0};
 
    visited[A] = 1;
    q.push({A, ""});
    
    while(!q.empty())
    {
        int now = q.front().first;
        string com = q.front().second;
        q.pop();
        
        if(now == B)
        {
            cout << com << "\n";
            return;
        }
        
        for(int i = 1; i <= 4; i++)
        {
            // D
            if(i == 1)
            {
                int num = now * 2;
                
                if(num > 9999)
                {
                    num %= 10000;
                }
 
                if(visited[num] == 0)
                {
                    visited[num] = 1;
                    q.push({num, com+"D"});
                }
            }
            // S
            else if(i == 2)
            {
                int num = now;
                
                if(num == 0)
                {
                    num = 9999;
                }
                else
                {
                    num -= 1;    
                }
                
                if(visited[num] == 0)
                {
                    visited[num] = 1;
                    q.push({num, com+"S"});
                }
            }
            // L
            else if(i == 3)
            {
                int num = now;
                
                int a = num % 1000;
                int b = num / 1000;
                
                num = a*10 + b;
 
                if(visited[num] == 0)
                {
                    visited[num] = 1;
                    q.push({num, com+"L"});
                }
            }
            // R
            else if(i == 4)
            {
                int num = now;
                
                int a = num / 10;
                int b = num % 10;
                
                num = a + b*1000;
 
                if(visited[num] == 0)
                {
                    visited[num] = 1;
                    q.push({num, com+"R"});
                }
            }
        }
    }
}
    
int main(void)
{
//    freopen("B9019_input.txt", "r", stdin);
    
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    
    cin >> T;
    
    for(int n = 1; n <= T; n++)
    {
        cin >> A >> B;
        
        BFS();
    }    
    
    return 0;
}
cs
저작자표시

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

[백준 1194] 달이 차오른다, 가자. (BFS, Bitmask) (C/C++) (★★★)  (0) 2019.12.11
[백준 3197] 백조의 호수 (BFS) (C/C++) (★★★)  (0) 2019.12.09
[백준 11559] Puyo Puyo (BFS) (C/C++) (★)  (0) 2019.12.08
[백준 16234] 인구이동 (BFS) (C/C++) (★★)  (0) 2019.12.07
[백준 2573] 빙산 (BFS) (C/C++) (★)  (0) 2019.12.06
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
 
char map[12][6];
int ans;
bool bombFlag = false;
 
queue<pair<int, int>> q;
int visited[12][6];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
void init()
{
    for(int i = 0; i < 12; i++)
    {
        for(int j = 0; j < 6; j++)
        {
            visited[i][j] = 0;
        }
    }
}
 
int safe(int x, int y)
{
    if(x >= 0 && x < 12 && y >= 0 && y < 6)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void down()
{
    for(int j = 0; j < 6; j++)
    {
        for(int i = 11; i >= 0; i--)
        {
            if(map[i][j] != '.')
            {
                for(int k = 11; k > i; k--)
                {
                    if(map[k][j] == '.')
                    {
                        map[k][j] = map[i][j];
                        map[i][j] = '.';
                        break;
                    }
                }
            }
        }
    }
}
 
/*
void down()
{    
    // ↓이기때문에 열을 기준으로 
    for(int j = 0; j < 6; j++)
    {
        // 아래에서부터 위로 
        for(int i = 11; i >= 0; i--)
        {
            if(map[i][j] != '.')
            {
                enqueue(map[i][j]);
                map[i][j] = '.';
            }
        }
        
        int idx = 11;
        while(front != rear)
        {
            char temp = dequeue();
            map[idx--][j] = temp;
        }
    }
}
*/
 
void bomb(int x, int y, char color)
{
    int cnt = 0;
    vector<pair<int, int>> crash;
    
    visited[x][y] = 1;
    q.push({x, y});
    
    crash.push_back({x, y});
    cnt++;
    
    while(!q.empty())
    {
        x = q.front().first;
        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] == color)
            {
                visited[xpos][ypos] = 1;
                q.push({xpos, ypos});
                
                crash.push_back({xpos, ypos});
                cnt++;
            }
        }
    }
    
    if(cnt >= 4)
    {
        for(int i = 0; i < crash.size(); i++)
        {
            map[crash[i].first][crash[i].second] = '.';
        }
        
        bombFlag = true;
    }
}
 
int main(void)
{
//    freopen("B11559_input.txt", "r", stdin);
    
    for(int i = 0; i < 12; i++)
    {
        for(int j = 0; j < 6; j++)
        {
            scanf(" %c", &map[i][j]);
        }
    }
    
    while(1)
    {
        bombFlag = false;
        bool breakFlag = true;
        
        memset(visited, 0, sizeof(visited));
        
        for(int i = 0; i < 12; i++)
        {
            for(int j = 0; j < 6; j++)
            {
                if(visited[i][j] == 0 && map[i][j] != '.')
                {            
                     bomb(i, j, map[i][j]);
                }
            }
        }
        
        if(bombFlag == true)
        {
            breakFlag = false;
            ans++;                                
        }
        
        if(breakFlag == true)
        {
            printf("%d", ans);
            break;
        }
        
        down();
    }
    
    return 0; 
}
cs
저작자표시

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

[백준 3197] 백조의 호수 (BFS) (C/C++) (★★★)  (0) 2019.12.09
[백준 9019] DSLR (BFS) (C/C++)  (0) 2019.12.08
[백준 16234] 인구이동 (BFS) (C/C++) (★★)  (0) 2019.12.07
[백준 2573] 빙산 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 1389] 케빈 베이컨의 6단계 법칙 (BFS) (C/C++)  (0) 2019.12.06
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
 
int map[110][110];
int N, L, R;
 
queue<pair<int, int>> q;
int visited[110][110];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && x < N && y >= 0 && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void init()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            visited[i][j] = 0;
        }
    }    
}
 
int check()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(visited[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
void BFS(int x, int y)
{
    // 시간초과의 원인
    // int check[110][110] = {0};
    vector<pair<int, int>> check;
    
    q.push({x, y});
    
    int sum = 0;
    int cnt = 0;
    while(!q.empty())
    {
        x = q.front().first;
        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 && L <= abs(map[xpos][ypos]-map[x][y]) && abs(map[xpos][ypos]-map[x][y]) <= R)
            {
                if(visited[x][y] == 0)
                {
                    // 시간초과의 원인
                    // check[x][y] = 1;
                    check.push_back({x, y});
                    
                    visited[x][y] = 1;
                    
                    sum += map[x][y];
                    cnt++;
                }
                
                if(visited[xpos][ypos] == 0)
                {
                    // 시간초과의 원인 
                    // check[xpos][ypos] = 1;
                    check.push_back({xpos, ypos});
                    
                    visited[xpos][ypos] = 1;
                    q.push({xpos, ypos});
                    
                    sum += map[xpos][ypos];
                    cnt++;
                }
            }
        }
    }
    
    // 시간초과의 원인 
    /*
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(check[i][j] == 1)
            {
                map[i][j] = sum/cnt;
            }
        }
    }
    */
    
    // 이동 후 초기화 
    for(int i = 0; i < check.size(); i++)
    {
        map[check[i].first][check[i].second] = sum/cnt;
    }
}
 
int main(void)
{
//    freopen("B16234_input.txt", "r", stdin);
    
    scanf("%d %d %d", &N, &L, &R);
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
    
    int ans = 0;
    while(1)
    {
//        init();
        memset(visited, 0 ,sizeof(visited));
        
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                if(visited[i][j] == 0)
                {
                    BFS(i, j);    
                }
            }
        }    
        
        if(check() == 1)
        {
            printf("%d", ans);
            break;
        }
        
        ans++;
    }
    
    return 0;
}
cs
저작자표시

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

[백준 9019] DSLR (BFS) (C/C++)  (0) 2019.12.08
[백준 11559] Puyo Puyo (BFS) (C/C++) (★)  (0) 2019.12.08
[백준 2573] 빙산 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 1389] 케빈 베이컨의 6단계 법칙 (BFS) (C/C++)  (0) 2019.12.06
[백준 1261] 알고스팟 (BFS) (C/C++) (★)  (0) 2019.12.06
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
int map[310][310];
int mapCopy[310][310];
int visited[310][310];
int row, col;
int time;
 
queue<pair<int, int>> q;
 
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 init()
{
    for(int x = 0; x < row; x++)
    {
        for(int y = 0; y < col; y++)
        {
            int cnt = 0;
            
            for(int k = 0; k < 4; k++)
            {
                int xpos = x+dx[k];
                int ypos = y+dy[k];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 0)
                {
                    cnt++;        
                }
            }
            
            if(cnt != 0)
            {
                q.push({x, y});
            }
        }
    }
}
 
void melt()
{
    int size = q.size();
    
    while(size--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        int cnt = 0;
        
        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)
            {
                cnt++;
            }    
        }    
        
        mapCopy[x][y] -= cnt;
        
        if(mapCopy[x][y] < 0)
        {
            mapCopy[x][y] = 0;
        }    
    }
}
 
void check(int x, int y)
{
    queue<pair<int, int>> c;
    c.push({x, y});
    visited[x][y] = 1;
    
    while(!c.empty())
    {
        x = c.front().first;
        y = c.front().second;
        c.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] != 0 && visited[xpos][ypos] == 0)
            {
                c.push({xpos, ypos});
                visited[xpos][ypos] = 1;
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2589_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
            
            mapCopy[i][j] = map[i][j];
        }
    }
    
    while(1)
    {    
        time++;
        
        init();
        
        melt();
        
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                map[i][j] = mapCopy[i][j];
            }
        }
        
        int mapCnt = 0;
        memset(visited, 0, sizeof(visited));
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] != 0 && visited[i][j] == 0)
                {
                    check(i, j);
                    mapCnt++;
                }
            }
        }
        
        if(mapCnt >= 2)
        {
            cout << time;
            break;
        }
        else if(mapCnt == 0)
        {
            cout << "0";
            break;
        }
    }
    
    return 0;
}
 cs
저작자표시

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

[백준 11559] Puyo Puyo (BFS) (C/C++) (★)  (0) 2019.12.08
[백준 16234] 인구이동 (BFS) (C/C++) (★★)  (0) 2019.12.07
[백준 1389] 케빈 베이컨의 6단계 법칙 (BFS) (C/C++)  (0) 2019.12.06
[백준 1261] 알고스팟 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 14395] 4연산 (BFS) (C/C++)  (0) 2019.12.06

+ Recent posts

티스토리툴바