#include <iostream>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <string>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int cnt;
    int time;
}node;
 
int row, col, K;
int Map[1010][1010];
int visited[1010][1010][12][2];
int Min = 99999999;
 
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
 
int safe(int x, int y)
{
    if(1 <= x && x <= row && 1 <= y && y <= col)
    {
        return 1;
    }
    
    return 0;
}
 
void BFS()
{
    queue<node> q;
    
    q.push({1, 1, 0, 0});
    visited[1][1][0][0] = 1;
    
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        int time = q.front().time;
        q.pop();
        
        if(x == row && y == col)
        {
            Min = visited[x][y][cnt][time];
            return;
        }
        
        for(int i = 0; i < 4; i++)
        {
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(safe(nx, ny) == 0)
            {
                continue;
            }
            
            if(time == 0)
            {
                // 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.
                if(visited[x][y][cnt][1] == 0)
                {
                    q.push({x, y, cnt, 1});
                    visited[x][y][cnt][1] = visited[x][y][cnt][0] + 1;
                }
                
                if(Map[nx][ny] == 0 && visited[nx][ny][cnt][1] == 0)
                {
                    q.push({nx, ny, cnt, 1});
                    visited[nx][ny][cnt][1] = visited[x][y][cnt][0] + 1;
                }
                else if(Map[nx][ny] == 1 && visited[nx][ny][cnt+1][1] == 0 && cnt+1 <= K)
                {
                    q.push({nx, ny, cnt+1, 1});
                    visited[nx][ny][cnt+1][1] = visited[x][y][cnt][0] + 1;
                }
            }
            else if(time == 1)
            {
                // 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.
                if(visited[x][y][cnt][0] == 0)
                {
                    q.push({x, y, cnt, 0});
                    visited[x][y][cnt][0] = visited[x][y][cnt][1] + 1;
                }
                
                if(Map[nx][ny] == 0 && visited[nx][ny][cnt][0] == 0)
                {
                    q.push({nx, ny, cnt, 0});
                    visited[nx][ny][cnt][0] = visited[x][y][cnt][1] + 1;
                }
            }
        }    
    }
}
 
int main(void)
{
//    freopen("B14442_input.txt", "r", stdin);
    
    cin >> row >> col >> K;
    
    for(int i = 1; i <= row; i++)
    {
        for(int j = 1; j <= col; j++)
        {
            scanf("%1d", &Map[i][j]);
        }
    }
    
    BFS();
    
    if(Min == 99999999)
    {
        cout << "-1";
    }
    else
    {
        cout << Min;    
    }
    
    return 0;
}
cs
저작자표시

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

[백준 17471] 게리맨더링 (DFS) (C/C+) (★)  (0) 2021.01.17
[백준 5213] 과외맨 (BFS) (C/C++) (★★)  (0) 2020.05.26
[백준 1939] 중량제한 (BFS, BinarySearch) (C/C++) (★★★)  (0) 2020.05.24
[백준 4991] 로봇 청소기 (BFS, Bitmask) (C/C++) (★★★)  (0) 2020.05.21
[백준 2638] 치즈 (BFS) (C/C++) (★★★)  (0) 2020.04.07
#include <iostream>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <string>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int N;
int num[15];
vector<int> area[15];
vector<int> red;
int Min = 999999999;
 
int blue_check(vector<int> blue, int visited[15])
{
    queue<int> q;
    q.push(blue[0]);
    visited[blue[0]] = 1;
    int cnt = 1;
    
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        
        for(int i = 0; i < area[now].size(); i++)
        {
            int next = area[now][i];
            
            if(visited[next] == 0)
            {
                q.push(next);
                visited[next] = 1;
                cnt++;
            }
        }
    }
    
    if(cnt == blue.size())
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int red_check(int visited[15])
{
    queue<int> q;
    q.push(red[0]);
    visited[red[0]] = 1;
    int cnt = 1;
    
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        
        for(int i = 0; i < area[now].size(); i++)
        {
            int next = area[now][i];
            
            if(visited[next] == 0)
            {
                q.push(next);
                visited[next] = 1;
                cnt++;
            }
        }    
    }
    
    if(cnt == red.size())
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void combination(int idx, int cnt, int finish)
{
    if(cnt == finish)
    {
        vector<int> blue;
        int red_visited[15] = {0};
        int blue_visited[15] = {0};
        int sum1 = 0;
        int sum2 = 0;
 
        for(int i = 0; i < red.size(); i++)
        {
            blue_visited[red[i]] = 1;
            sum1 += num[red[i]];
        }
        
        for(int i = 1; i <= N; i++)
        {
            if(blue_visited[i] == 0)
            {
                red_visited[i] = 1;
                blue.push_back(i);
                sum2 += num[i];
            }
        }
        
        if(red_check(red_visited) == 1)
        {
            if(blue_check(blue, blue_visited) == 1)
            {
                Min = min(Min, abs(sum1-sum2));
            }    
        }
        
        return;    
    }
    
    for(int i = idx; i <= N; i++)
    {
        red.push_back(i);
        combination(i+1, cnt+1, finish);
        red.pop_back();
    }
}
 
int main(void)
{
//    freopen("B17471_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> num[i];
    }
    
    for(int from = 1; from <= N; from++)
    {
        int M; 
        cin >> M;
        
        for(int i = 1; i <= M; i++)
        {
            int to;
            cin >> to;
            
            area[from].push_back(to);
            area[to].push_back(from);
        }
    }
    
    for(int i = 1; i <= N/2; i++)
    {
        combination(1, 0, i);
    }
    
    if(Min == 999999999)
    {
        cout << "-1";
    }
    else
    {
        cout << Min;    
    }
    
    return 0;
}
cs
저작자표시

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

[백준 16933] 벽 부수고 이동하기3 (BFS) (C/C+)  (0) 2021.01.19
[백준 5213] 과외맨 (BFS) (C/C++) (★★)  (0) 2020.05.26
[백준 1939] 중량제한 (BFS, BinarySearch) (C/C++) (★★★)  (0) 2020.05.24
[백준 4991] 로봇 청소기 (BFS, Bitmask) (C/C++) (★★★)  (0) 2020.05.21
[백준 2638] 치즈 (BFS) (C/C++) (★★★)  (0) 2020.04.07
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
 
int N;
pair<int, int> Map[510][1020]; // 타일숫자, 타일번호 
int visited[510][1020];
int path[510*1020];
int tileNum;
int last; 
vector<int> trace;
 
int dx[4] = {-1, 1, 0, 0}; // 상하좌우 
int dy[4] = {0, 0, -1, 1}; // 상하좌우 
 
void BFS()
{
    queue<pair<int, int>> q;
    q.push({1, 1});
    q.push({1, 2});
    visited[1][1] = 1;
    visited[1][2] = 1;
    
    path[1] = 0; // 0번(초기화용 타일번호) -> 1번(시작 타일번호) 
    
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
 
        if(Map[x][y].second == tileNum)
        {
//            cout << visited[x][y] << endl;
            last = Map[x][y].second;
            return;
        }
        else
        {
            last = max(last, Map[x][y].second);
        }
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(visited[xpos][ypos] != 0 || Map[xpos][ypos].first == 0 || Map[xpos][ypos].second == 0)
            {
                continue;
            }
            
            // (타일 번호가 다르고) 타일의 숫자가 같은 경우
            if(Map[x][y].second != Map[xpos][ypos].second && Map[x][y].first == Map[xpos][ypos].first)
            {
                q.push({xpos, ypos});
                visited[xpos][ypos] = visited[x][y]+1;
                path[Map[xpos][ypos].second] = Map[x][y].second;
                
                // 타일 번호가 같은 타일 숫자 왼쪽, 오른쪽 확인 후 큐에 삽입 
                if(Map[xpos][ypos-1].second == Map[xpos][ypos].second)
                {
                    q.push({xpos, ypos-1});    
                    visited[xpos][ypos-1] = visited[xpos][ypos];
                }
                else if(Map[xpos][ypos].second == Map[xpos][ypos+1].second)
                {
                    q.push({xpos, ypos+1});    
                    visited[xpos][ypos+1] = visited[xpos][ypos];
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B5213_input.txt", "r", stdin);
    
    cin >> N;
    
    int row = N;
    
    for(int k = 1; k <= row; k++)
    {
        // 홀수번째 row 
        if(k % 2 == 1)
        {
            for(int i = 1; i <= 2*N; i++)
            {
                if(i % 2 == 1)
                {
                    tileNum++;
                }
                
                int a;
                cin >> a;
                
                Map[k][i].first = a;
                Map[k][i].second = tileNum;
            }        
        }
        // 짝수번째 row
        else
        {
            for(int i = 2; i <= 2*N-1; i++)
            {
                if(i % 2 == 0)
                {
                    tileNum++;
                }
                
                int a;
                cin >> a;
                
                Map[k][i].first = a;
                Map[k][i].second = tileNum;
            }
        }
    }
 
    BFS();
    
    // 경로 구하는 과정 
    int idx = last;
    while(path[idx] != 0)
    {
        trace.push_back(idx);
        idx = path[idx];
    }
    trace.push_back(1);
    
    cout << trace.size() << endl;
    for(int i = trace.size()-1; i >= 0; i--)
    {
        cout << trace[i] << " ";
    }
        
    return 0;
}
cs
저작자표시

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

[백준 16933] 벽 부수고 이동하기3 (BFS) (C/C+)  (0) 2021.01.19
[백준 17471] 게리맨더링 (DFS) (C/C+) (★)  (0) 2021.01.17
[백준 1939] 중량제한 (BFS, BinarySearch) (C/C++) (★★★)  (0) 2020.05.24
[백준 4991] 로봇 청소기 (BFS, Bitmask) (C/C++) (★★★)  (0) 2020.05.21
[백준 2638] 치즈 (BFS) (C/C++) (★★★)  (0) 2020.04.07
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
 
int N, M;
vector<pair<int, long long>> v[10010];
int start, arrive;
long long Max;
long long MaxCost;
 
bool BFS(int limit)
{
    queue<int> q;
    int visited[10010] = {0};
    
    q.push(start);
    visited[start] = 1;
    
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        
        if(x == arrive)
        {
            return true;
        }
        
        for(int i = 0; i < v[x].size(); i++)
        {
            if(visited[v[x][i].first] == 0 && v[x][i].second >= limit)
            {
                visited[v[x][i].first] = 1;
                q.push(v[x][i].first);
            }
        }
    }
    
    return false;
}
 
int main(void)
{
//    freopen("B1939_input.txt", "r", stdin);
    
    cin >> N >> M;
    
    for(int i = 1; i <= M; i++)
    {
        int from, to;
        long long cost;
        cin >> from >> to >> cost;
        
        v[from].push_back({to, cost});
        v[to].push_back({from, cost});
        
        MaxCost = max(MaxCost, cost);
    }
    
    cin >> start >> arrive;
    
    long long left = 1;
    long long right = MaxCost;
    
    while(left <= right)
    {
        long long mid = (left + right) / 2;
        
        if(BFS(mid))
        {
            left = mid+1;    
            Max = mid;
        }
        else
        {
            right = mid-1;
        }
    }
    
    cout << Max << endl;
        
    return 0;
}
cs
저작자표시

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

[백준 17471] 게리맨더링 (DFS) (C/C+) (★)  (0) 2021.01.17
[백준 5213] 과외맨 (BFS) (C/C++) (★★)  (0) 2020.05.26
[백준 4991] 로봇 청소기 (BFS, Bitmask) (C/C++) (★★★)  (0) 2020.05.21
[백준 2638] 치즈 (BFS) (C/C++) (★★★)  (0) 2020.04.07
[백준 2589] 보물섬 (BFS) (C/C++)  (0) 2020.04.07
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string>
#include <string.h>
using namespace std;
 
typedef struct dNode
{
    int x;
    int y;
    int dirtyNum;
}dNode;
 
typedef struct qNode
{
    int x;
    int y;
    int clearDirty;
    int dist;
}qNode;
 
char Map[25][25];
int visited[25][25][1 << 11];
int row, col;
vector<dNode> dirty;
int dirtyCnt;
int clear;
int ans = -1;
 
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()
{
    queue<qNode> q;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(Map[i][j] == 'o')
            {
                q.push({i, j, 0, 0});
                visited[i][j][0] = 1;
                break;
            }
        }
    }
    
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int clearDirty = q.front().clearDirty;
        int dist = q.front().dist;
        q.pop();
        
        if(clear == clearDirty)
        {
            ans = dist;
            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] != 'x' && visited[xpos][ypos][clearDirty] == 0)
            {
                visited[xpos][ypos][clearDirty] = 1;
                q.push({xpos, ypos, clearDirty, dist+1});
            } 
            // 더러운 곳인 경우 
            else if(safe(xpos, ypos) == 1 && Map[xpos][ypos] == '*' && visited[xpos][ypos][clearDirty] == 0)
            {
                int findNum;
                
                for(int j = 0; j < dirty.size(); j++)
                {
                    if(dirty[j].x == xpos && dirty[j].y == ypos)
                    {
                        findNum = dirty[j].dirtyNum;
                        break;        
                    }
                }
                                
                // 깨끗하게 만들지 않은 칸이면
                if((clearDirty & (1 << findNum-1)) == 0)
                {
                    int tempClearDirty = clearDirty;
                    tempClearDirty += (1 << findNum-1);
                    
                    visited[xpos][ypos][tempClearDirty] = 1;
                    q.push({xpos, ypos, tempClearDirty, dist+1});
                }
                // 깨끗하게 만든 칸이면
                else
                {
                    visited[xpos][ypos][clearDirty] = 1;
                    q.push({xpos, ypos, clearDirty, dist+1});
                }     
            }
        }
    }
}
 
int main(void)
{
//    freopen("B4991_input.txt", "r", stdin);
    
    while(1)
    {
        memset(visited, 0, sizeof(visited));
        dirty.clear();
        dirtyCnt = 0;
        ans = -1;
        
        cin >> col >> row;
    
        if(row == 0 && col == 0)
        {
            return 0;
        }
        
        for(int i = 0; i < row; i++)
        {
            string temp;
            cin >> temp;
            
            for(int j = 0; j < temp.size(); j++)
            {
                Map[i][j] = temp[j];
                
                // 비트 연산을 위해 더러운 곳에 번호 부여 
                if(Map[i][j] == '*')
                {
                    dirty.push_back({i, j, ++dirtyCnt});
                }
            }
        }
        
        // 더러운 곳을 모두 채웠을 때의 비트 값 
        clear = (1 << dirtyCnt) - 1;
        
        BFS();
        
        cout << ans << endl;
    }
    
    return 0;
}
 cs
저작자표시

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

[백준 5213] 과외맨 (BFS) (C/C++) (★★)  (0) 2020.05.26
[백준 1939] 중량제한 (BFS, BinarySearch) (C/C++) (★★★)  (0) 2020.05.24
[백준 2638] 치즈 (BFS) (C/C++) (★★★)  (0) 2020.04.07
[백준 2589] 보물섬 (BFS) (C/C++)  (0) 2020.04.07
[백준 1938] 통나무 옮기기 (BFS) (C/C++) (★★★)  (0) 2020.02.19
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
int map[110][110];
int visited[110][110];
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 paint(int x, int y, int level)
{
    queue<pair<int, int>> c;
    c.push({x, y});
    visited[x][y] = 1;
    
    while(!c.empty())
    {
        int x = c.front().first;
        int 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] != 1 && visited[xpos][ypos] == 0)
            {
                map[xpos][ypos] = level;
                c.push({xpos, ypos});
                visited[xpos][ypos] = 1;
            }
        }
    }
}
 
void init(int x, int 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] == 2)
        {
            cnt++;
        }
    }
    
    if(cnt >= 2)
    {
        q.push({x, y});
    }
}
 
void melt()
{
    int size = q.size();
    
    while(size--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        map[x][y] = 2;
    }
}
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
int main(void)
{
//    freopen("B2638_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];
        }
    }
    
    // 치즈는 1, 바깥쪽은 2, 안쪽은 3~ 색칠 
    int level = 2;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0)
            {
                paint(i, j, level);
                level++;    
            }
        }
    }
    
    while(1)
    {    
        memset(visited, 0, sizeof(visited));
        
        time++;
        
        // 바깥쪽과 2면 이상 접촉하는 치즈, 큐에 삽입 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 1)
                {
                    init(i, j);            
                }
            }
        }
        
        melt();
        
        // 치즈가 녹아서 바깥쪽과 안쪽이 연결되었으면 다시 2로 색칠 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 2 && visited[i][j] == 0)
                {
                    paint(i, j, 2);
                }
            }
        }
        
        if(check() == 1)
        {
            cout << time;
            break;
        }
    }
    
    return 0;
}
cs
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
int map[110][110];
int visited[110][110];
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 paint(int x, int y, int level)
{
    queue<pair<int, int>> c;
    c.push({x, y});
    visited[x][y] = 1;
    
    while(!c.empty())
    {
        int x = c.front().first;
        int 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] != 1 && visited[xpos][ypos] == 0)
            {
                map[xpos][ypos] = level;
                c.push({xpos, ypos});
                visited[xpos][ypos] = 1;
            }
        }
    }
}
 
void init(int x, int 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] == 2)
        {
            cnt++;
        }
    }
    
    if(cnt >= 2)
    {
        q.push({x, y});
    }
}
 
void melt()
{
    int size = q.size();
    
    while(size--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        map[x][y] = 2;
    }
}
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
int main(void)
{
//    freopen("B2638_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];
        }
    }
    
    // 치즈는 1, 바깥쪽은 2, 안쪽은 3~ 색칠 
    int level = 2;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0)
            {
                paint(i, j, level);
                level++;    
            }
        }
    }
    
    while(1)
    {    
        memset(visited, 0, sizeof(visited));
        
        time++;
        
        // 바깥쪽과 2면 이상 접촉하는 치즈, 큐에 삽입 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 1)
                {
                    init(i, j);            
                }
            }
        }
        
        melt();
        
        // 치즈가 녹아서 바깥쪽과 안쪽이 연결되었으면 다시 2로 색칠 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 2 && visited[i][j] == 0)
                {
                    paint(i, j, 2);
                }
            }
        }
        
        if(check() == 1)
        {
            cout << time;
            break;
        }
    }
    
    return 0;
}
cs
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
int map[110][110];
int visited[110][110];
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 paint(int x, int y, int level)
{
    queue<pair<int, int>> c;
    c.push({x, y});
    visited[x][y] = 1;
    
    while(!c.empty())
    {
        int x = c.front().first;
        int 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] != 1 && visited[xpos][ypos] == 0)
            {
                map[xpos][ypos] = level;
                c.push({xpos, ypos});
                visited[xpos][ypos] = 1;
            }
        }
    }
}
 
void init(int x, int 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] == 2)
        {
            cnt++;
        }
    }
    
    if(cnt >= 2)
    {
        q.push({x, y});
    }
}
 
void melt()
{
    int size = q.size();
    
    while(size--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        map[x][y] = 2;
    }
}
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
int main(void)
{
//    freopen("B2638_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];
        }
    }
    
    // 치즈는 1, 바깥쪽은 2, 안쪽은 3~ 색칠 
    int level = 2;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0)
            {
                paint(i, j, level);
                level++;    
            }
        }
    }
    
    while(1)
    {    
        memset(visited, 0, sizeof(visited));
        
        time++;
        
        // 바깥쪽과 2면 이상 접촉하는 치즈, 큐에 삽입 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 1)
                {
                    init(i, j);            
                }
            }
        }
        
        melt();
        
        // 치즈가 녹아서 바깥쪽과 안쪽이 연결되었으면 다시 2로 색칠 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 2 && visited[i][j] == 0)
                {
                    paint(i, j, 2);
                }
            }
        }
        
        if(check() == 1)
        {
            cout << time;
            break;
        }
    }
    
    return 0;
}
cs
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
int map[110][110];
int visited[110][110];
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 paint(int x, int y, int level)
{
    queue<pair<int, int>> c;
    c.push({x, y});
    visited[x][y] = 1;
    
    while(!c.empty())
    {
        int x = c.front().first;
        int 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] != 1 && visited[xpos][ypos] == 0)
            {
                map[xpos][ypos] = level;
                c.push({xpos, ypos});
                visited[xpos][ypos] = 1;
            }
        }
    }
}
 
void init(int x, int 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] == 2)
        {
            cnt++;
        }
    }
    
    if(cnt >= 2)
    {
        q.push({x, y});
    }
}
 
void melt()
{
    int size = q.size();
    
    while(size--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        map[x][y] = 2;
    }
}
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
int main(void)
{
//    freopen("B2638_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];
        }
    }
    
    // 치즈는 1, 바깥쪽은 2, 안쪽은 3~ 색칠 
    int level = 2;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0)
            {
                paint(i, j, level);
                level++;    
            }
        }
    }
    
    while(1)
    {    
        memset(visited, 0, sizeof(visited));
        
        time++;
        
        // 바깥쪽과 2면 이상 접촉하는 치즈, 큐에 삽입 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 1)
                {
                    init(i, j);            
                }
            }
        }
        
        melt();
        
        // 치즈가 녹아서 바깥쪽과 안쪽이 연결되었으면 다시 2로 색칠 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 2 && visited[i][j] == 0)
                {
                    paint(i, j, 2);
                }
            }
        }
        
        if(check() == 1)
        {
            cout << time;
            break;
        }
    }
    
    return 0;
}
cs
저작자표시

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

[백준 1939] 중량제한 (BFS, BinarySearch) (C/C++) (★★★)  (0) 2020.05.24
[백준 4991] 로봇 청소기 (BFS, Bitmask) (C/C++) (★★★)  (0) 2020.05.21
[백준 2589] 보물섬 (BFS) (C/C++)  (0) 2020.04.07
[백준 1938] 통나무 옮기기 (BFS) (C/C++) (★★★)  (0) 2020.02.19
[백준 1261] 알고스팟 (BFS) (C/C++) (★★)  (0) 2020.02.16
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
char map[50][50];
int visited[50][50];
int row, col;
int Max;
 
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(int x, int y)
{
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = 1;
    
    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 && map[xpos][ypos] == 'L' && visited[xpos][ypos] == 0)
            {
                visited[xpos][ypos] = visited[x][y] + 1;
                q.push({xpos, ypos});
                
                if(Max < visited[xpos][ypos])
                {
                    Max = visited[xpos][ypos];
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2589_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        string input;
        cin >> input;
        
        for(int j = 0; j < col; j++)
        {
            map[i][j] = input[j];
        }
    }
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 'L')
            {
                memset(visited, 0, sizeof(visited));
                BFS(i, j);
            }
        }
    }
    
    cout << Max-1;
    
    return 0;
}
 
cs
저작자표시

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

[백준 4991] 로봇 청소기 (BFS, Bitmask) (C/C++) (★★★)  (0) 2020.05.21
[백준 2638] 치즈 (BFS) (C/C++) (★★★)  (0) 2020.04.07
[백준 1938] 통나무 옮기기 (BFS) (C/C++) (★★★)  (0) 2020.02.19
[백준 1261] 알고스팟 (BFS) (C/C++) (★★)  (0) 2020.02.16
[백준 1167] 트리의 지름 (BFS, Tree) (C/C++) (★)  (0) 2020.02.16
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int shape;
}node;
 
char map[55][55];
int visited[55][55][2]; // 가로모양, 세로모양 
int N;
bool Move = false;
 
int first_B_x, first_B_y;
int first_E_x, first_E_y;
int mid_B_x, mid_B_y;
int mid_E_x, mid_E_y;
int B_shape;
int E_shape;
 
queue<node> q;
 
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;
    }
}
 
int check(int x, int y)
{
    for(int i = x-1; i <= x+1; i++)
    {
        for(int j = y-1; j <= y+1; j++)
        {
            if(safe(i, j) == 0)
            {
                return 0;
            }
            else if(safe(i, j) == 1)
            {
                if(map[i][j] == '1')
                {
                    return 0;
                }
            }
        }
    }
    
    return 1;
}
 
void BFS(int x, int y, int shape)
{
    visited[x][y][shape] = 1;
    q.push({x, y, shape});
    
    while(!q.empty())
    {
        x = q.front().x;
        y = q.front().y;
        shape = q.front().shape;
        q.pop();
        
        if(x == mid_E_x && y == mid_E_y && shape == E_shape)
        {
            Move = true;
            return;
        }
        
        // 상하좌우 
        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][shape] == 0 && map[xpos][ypos] != '1')
            {
                // 가로 
                if(shape == 0)
                {
                    if(safe(xpos, ypos-1) == 1 && safe(xpos, ypos+1) == 1 && map[xpos][ypos-1] != '1' && map[xpos][ypos+1] != '1')
                    {
                        visited[xpos][ypos][shape] = visited[x][y][shape]+1;
                        q.push({xpos, ypos, shape});
                    }
                }
                // 세로 
                else if(shape == 1)
                {
                    if(safe(xpos-1, ypos) == 1 && safe(xpos+1, ypos) == 1 && map[xpos-1][ypos] != '1' && map[xpos+1][ypos] != '1')
                    {
                        visited[xpos][ypos][shape] = visited[x][y][shape]+1;
                        q.push({xpos, ypos, shape});
                    }
                }
            }
        }
        
        // 회전 
        if(check(x, y) == 1)
        {
            // 가로 -> 세로 
            if(shape == 0)
            {
                if(visited[x][y][1] == 0)
                {
                    visited[x][y][1] = visited[x][y][0]+1;
                    q.push({x, y, 1});
                }
            }
            // 세로 -> 가로 
            else if(shape == 1)
            {
                if(visited[x][y][0] == 0)
                {
                    visited[x][y][0] = visited[x][y][1]+1;
                    q.push({x, y, 0});
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1938_input.txt", "r", stdin);
 
    cin >> N;
    
    int find_mid_B = 1;
    int find_mid_E = 1;
    
    for(int i = 0; i < N; i++)
    {
        string input;
        cin >> input;
        
        for(int j = 0; j < N; j++)
        {
            map[i][j] = input[j];
            
            if(map[i][j] == 'B' && find_mid_B == 1)
            {
                first_B_x = i;
                first_B_y = j;
                
                find_mid_B++;
            }
            else if(map[i][j] == 'B' && find_mid_B == 2)
            {
                mid_B_x = i;
                mid_B_y = j;
                
                find_mid_B++;
            }
            
            if(map[i][j] == 'E' && find_mid_E == 1)
            {
                first_E_x = i;
                first_E_y = j;
                
                find_mid_E++;
            }
            else if(map[i][j] == 'E' && find_mid_E == 2)
            {
                mid_E_x = i;
                mid_E_y = j;
                
                find_mid_E++;
            }
        }
    }
    
    // 출발 통나무 - 가로 
    if(first_B_x - mid_B_x == 0)
    {
        B_shape = 0;
    }
    // 출발 통나무 - 세로 
    else if(first_B_x - mid_B_x == -1)
    {
        B_shape = 1;
    }
    
    // 도착 통나무 - 가로 
    if(first_E_x - mid_E_x == 0)
    {
        E_shape = 0;
    }
    // 도착 통나무 - 세로 
    else if(first_E_x - mid_E_x == -1)
    {
        E_shape = 1;
    }
    
    BFS(mid_B_x, mid_B_y, B_shape);
    
    if(Move == false)
    {
        cout << "0";
    }
    else
    {
        cout << visited[mid_E_x][mid_E_y][E_shape]-1;
    }
           
    return 0; 
}  
cs
저작자표시

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

[백준 2638] 치즈 (BFS) (C/C++) (★★★)  (0) 2020.04.07
[백준 2589] 보물섬 (BFS) (C/C++)  (0) 2020.04.07
[백준 1261] 알고스팟 (BFS) (C/C++) (★★)  (0) 2020.02.16
[백준 1167] 트리의 지름 (BFS, Tree) (C/C++) (★)  (0) 2020.02.16
[백준 1967] 트리의 지름 (BFS, Tree) (C/C++)  (0) 2020.02.16

+ Recent posts

티스토리툴바