#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int cnt;
}node;
 
int map[1010][1010];
int row, col, crash;
int Min = 99999999;
 
queue<node> q;
int visited[1010][1010][11];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 1 && x <= row && y >= 1 && y <= col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS()
{
    visited[1][1][0] = 1;
    q.push({1, 1, 0});
    
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        q.pop();
        
        if(x == row && y == col)
        {
            if(visited[row][col][cnt] < Min)
            {
                Min = visited[row][col][cnt];
            }
        }
        
        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][cnt+1] == 0 && cnt+1 <= crash)
            {
                visited[xpos][ypos][cnt+1] = visited[x][y][cnt] + 1;
                q.push({xpos, ypos, cnt+1});
            }
            else if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 0 && visited[xpos][ypos][cnt] == 0 && cnt <= crash)
            {
                visited[xpos][ypos][cnt] = visited[x][y][cnt] + 1;
                q.push({xpos, ypos, cnt});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B14442_input.txt", "r", stdin);
    
    scanf("%d %d %d", &row, &col, &crash);
    
    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' 카테고리의 다른 글

[백준 2234] 성곽 (BFS) (C/C++) (★★)  (0) 2019.12.05
[백준 12886] 돌 그룹 (BFS) (C/C++) (★)  (0) 2019.12.05
[백준 2206] 벽 부수고 이동하기 (BFS) (C/C++)  (0) 2019.12.04
[백준 11724] 연결요소의 개수 (BFS) (C/C++)  (0) 2019.12.04
[백준 2468] 안전영역 (BFS) (C/C++)  (0) 2019.12.04
#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int cnt;
}node;
 
int map[1010][1010];
int row, col;
int Min = 99999999;
 
queue<node> q;
int visited[1010][1010][2];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 1 && x <= row && y >= 1 && y <= col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS()
{
    visited[1][1][0] = 1;
    q.push({1, 1, 0});
    
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        q.pop();
        
        if(x == row && y == col)
        {
            if(visited[row][col][cnt] < Min)
            {
                Min = visited[row][col][cnt];
            }
        }
        
        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][cnt+1] == 0 && cnt+1 <= 1)
            {
                visited[xpos][ypos][cnt+1] = visited[x][y][cnt] + 1;
                q.push({xpos, ypos, cnt+1});
            }
            else if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 0 && visited[xpos][ypos][cnt] == 0 && cnt <= 1)
            {
                visited[xpos][ypos][cnt] = visited[x][y][cnt] + 1;
                q.push({xpos, ypos, cnt});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2206_input.txt", "r", stdin);
    
    scanf("%d %d", &row, &col);
    
    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' 카테고리의 다른 글

[백준 12886] 돌 그룹 (BFS) (C/C++) (★)  (0) 2019.12.05
[백준 14442] 벽 부수고 이동하기2 (BFS) (C/C++) (★)  (0) 2019.12.04
[백준 11724] 연결요소의 개수 (BFS) (C/C++)  (0) 2019.12.04
[백준 2468] 안전영역 (BFS) (C/C++)  (0) 2019.12.04
[백준 9177] 단어 섞기 (DFS/BFS) (C/C++) (★★)  (0) 2019.12.04
#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int map[1010][1010];
int V, E;
 
queue<int> q;
int visited[1010];
 
void BFS(int start)
{
    visited[start] = 1;
    q.push(start);
    
    while(!q.empty())
    {
        start = q.front();
        q.pop();
        
        for(int i = 1; i <= V; i++)
        {
            if(map[start][i] == 1 && visited[i] == 0)
            {
                visited[i] = 1;
                q.push(i);        
            }
        }
    }
}
 
int main(void)
{
//    freopen("B11724_input.txt", "r", stdin);
    
    cin >> V >> E;
    
    for(int i = 1; i <= E; i++)
    {
        int a, b;
        cin >> a >> b;
        
        map[a][b] = 1;
        map[b][a] = 1;
    }
    
    int cnt = 0;
    for(int i = 1; i <= V; i++)
    {
        if(visited[i] == 0)
        {
            BFS(i);
            cnt++;    
        }
    }
    
    cout << cnt;
        
    return 0;
}
cs
저작자표시

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

[백준 14442] 벽 부수고 이동하기2 (BFS) (C/C++) (★)  (0) 2019.12.04
[백준 2206] 벽 부수고 이동하기 (BFS) (C/C++)  (0) 2019.12.04
[백준 2468] 안전영역 (BFS) (C/C++)  (0) 2019.12.04
[백준 9177] 단어 섞기 (DFS/BFS) (C/C++) (★★)  (0) 2019.12.04
[백준 7562] 나이트의 이동 (BFS) (C/C++)  (0) 2019.12.03
#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int map[110][110];
int N;
int safeArea = 1;
int minArea = 99999;
int maxArea = -99999;
 
queue<pair<int, int>> q;
int visited[110][110];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
void init()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            visited[i][j] = 0;
        }
    }
}
 
int safe(int x, int y)
{
    if(x >= 0 && x < N && y >= 0 && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS(int x, int y, int rain)
{
    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++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && visited[xpos][ypos] == 0 && map[xpos][ypos] > rain)
            {
                visited[xpos][ypos] = 1;
                q.push({xpos, ypos});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2468_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(maxArea < map[i][j])
            {
                maxArea = map[i][j];
            }
            
            if(minArea > map[i][j])
            {
                minArea = map[i][j];
            }
        }
    }
    
    // 영역의 최소, 최대 높이만큼만 비를 계산하면 됨 
    for(int k = minArea; k <= maxArea; k++)
    {
        int cnt = 0;
        init();
        
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                // 비에 따른 안전영역 계산     
                if(visited[i][j] == 0 && map[i][j] > k)
                {
                    BFS(i, j, k);
                    cnt++;
                }
            }
        }
        
        if(safeArea < cnt)
        {
            safeArea = cnt;
        }
    }
    
    cout << safeArea;
    
    return 0;
}
cs
저작자표시

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

[백준 2206] 벽 부수고 이동하기 (BFS) (C/C++)  (0) 2019.12.04
[백준 11724] 연결요소의 개수 (BFS) (C/C++)  (0) 2019.12.04
[백준 9177] 단어 섞기 (DFS/BFS) (C/C++) (★★)  (0) 2019.12.04
[백준 7562] 나이트의 이동 (BFS) (C/C++)  (0) 2019.12.03
[백준 2251] 물통 (BFS) (C/C++)  (0) 2019.12.02

DFS

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
string a, b, c;
int T;
bool beforeFlag = true;
bool afterFlag = false;
    
void init()
{
    // 소문자 & 대문자 counting 
    int abCnt[52] = {0};
    int cCnt[52] = {0};
    
    for(int i = 0; i < a.size(); i++)
    {
        if('A' <= a[i] && a[i] <= 'Z')
        {
            abCnt[a[i]-'A'+26]++;
        }
        else
        {
            abCnt[a[i]-'a']++;   
        }
    }    
    
    for(int i = 0; i < b.size(); i++)
    {
        if('A' <= b[i] && b[i] <= 'Z')
        {
            abCnt[b[i]-'A'+26]++;
        }
        else
        {
            abCnt[b[i]-'a']++;    
        }
    }    
    
    for(int i = 0; i < c.size(); i++)
    {
        if('A' <= c[i] && c[i] <= 'Z')
        {
            cCnt[c[i]-'A'+26]++;
        }
        else
        {
            cCnt[c[i]-'a']++;
        }
    }    
    
    for(int i = 0; i < 52; i++)
    {
        if(abCnt[i] != cCnt[i])
        {
            beforeFlag = false;
            return;
        }
    }
}
 
void backtracking(int aIdx, int bIdx, int cIdx, string result)
{
    if(afterFlag == true)
    {
        return;
    }
    
    if(result == c)
    {
        afterFlag = true;
        return;
    }
    
    if(a[aIdx] == c[cIdx] && aIdx < a.size())
    {
        backtracking(aIdx+1, bIdx, cIdx+1, result+a[aIdx]);    
    }
    
    if(b[bIdx] == c[cIdx] && bIdx < b.size())
    {
        backtracking(aIdx, bIdx+1, cIdx+1, result+b[bIdx]);    
    }
} 
 
int main(void)
{
//    freopen("B9177_input.txt", "r", stdin);
    
    cin >> T;
 
    for(int n = 1; n <= T; n++)
    {
        cin >> a >> b >> c;
        
        beforeFlag = true;
        afterFlag = false;
        
        init();
        
        // 소문자 & 대문자 갯수로 미리 판별 
        if(beforeFlag == false)
        {
            printf("Data set %d: no\n", n);
            continue;
        }
        
        backtracking(0, 0, 0, "");
        
        if(afterFlag == true)
        {
            printf("Data set %d: yes\n", n);
        }
        else
        {
            printf("Data set %d: no\n", n);
        }
    }
    
    return 0;
}
 cs

 

BFS

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
typedef struct node
{
    int aIdx;
    int bIdx;
    int cIdx;
}node;
 
string a, b, c;
int T;
bool flag = false;
 
queue<node> q;
int visited[210][210];
 
void init()
{
    for(int i = 0; i < 210; i++)
    {
        for(int j = 0; j < 210; j++)
        {
            visited[i][j] = 0;
        }
    }
}
 
void BFS()
{
    visited[0][0] = 1;
    q.push({0, 0, 0});
    
    while(!q.empty())
    {
        int aIdx = q.front().aIdx;
        int bIdx = q.front().bIdx;
        int cIdx = q.front().cIdx;
        q.pop();
        
        if(cIdx == c.size())
        {
            flag = true;
            return;
        }
        
        if(visited[aIdx+1][bIdx] == 0 && a[aIdx] == c[cIdx])
        {
            visited[aIdx+1][bIdx] = 1;
            q.push({aIdx+1, bIdx, cIdx+1});
        }
        
        if(visited[aIdx][bIdx+1] == 0 && b[bIdx] == c[cIdx])
        {
            visited[aIdx][bIdx+1] = 1;
            q.push({aIdx, bIdx+1, cIdx+1});
        }
    }
} 
 
int main(void)
{
//    freopen("B9177_input.txt", "r", stdin);
    
    cin >> T;
 
    for(int n = 1; n <= T; n++)
    {
        cin >> a >> b >> c;
        
        flag = false;
        
        init();
        
        BFS();
        
        if(flag == true)
        {
            printf("Data set %d: yes\n", n);
        }
        else
        {
            printf("Data set %d: no\n", n);
        }
    }
    
    return 0;
}
 cs
저작자표시

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

[백준 11724] 연결요소의 개수 (BFS) (C/C++)  (0) 2019.12.04
[백준 2468] 안전영역 (BFS) (C/C++)  (0) 2019.12.04
[백준 7562] 나이트의 이동 (BFS) (C/C++)  (0) 2019.12.03
[백준 2251] 물통 (BFS) (C/C++)  (0) 2019.12.02
[백준 5014] 스타트 링크 (BFS) (C/C++)  (0) 2019.12.02
#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int map[310][310];
int T;
int len;
int startX, startY, endX, endY;
 
queue<pair<int, int>> q;
int visited[310][310];
 
int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
 
void init()
{
    for(int i = 0; i < len; i++)
    {
        for(int j = 0; j < len; j++)
        {
            visited[i][j] = 0;
        }
    }
}
 
int safe(int x, int y)
{
    if(x >= 0 && x < len && y >= 0 && y < len)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS()
{
    visited[startX][startY] = 1;
    q.push({startX, startY});
    
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 8; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && visited[xpos][ypos] == 0)
            {
                visited[xpos][ypos] = visited[x][y] + 1;
                q.push({xpos, ypos});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B7562_input.txt", "r", stdin);
    
    scanf("%d", &T);
    
    for(int n = 1; n <= T; n++)
    {            
        cin >> len;
        cin >> startX >> startY >> endX >> endY;
        
        BFS();
        
        cout << visited[endX][endY]-1 << endl;
        
        init();
    }
        
    return 0;
}
cs
저작자표시

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

[백준 2468] 안전영역 (BFS) (C/C++)  (0) 2019.12.04
[백준 9177] 단어 섞기 (DFS/BFS) (C/C++) (★★)  (0) 2019.12.04
[백준 2251] 물통 (BFS) (C/C++)  (0) 2019.12.02
[백준 5014] 스타트 링크 (BFS) (C/C++)  (0) 2019.12.02
[백준 1697] 숨바꼭질 (BFS) (C/C++)  (0) 2019.12.02
#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int A, B, C;
int visited[201][201][201];
int check[201];
 
queue<int> q;
 
void BFS(int nowA, int nowB, int nowC)
{
    visited[nowA][nowB][nowC] = 1;
    q.push(nowA);
    q.push(nowB);
    q.push(nowC);
    
    // C의 용량 체크 
    check[nowC] = 1;
    
    while(!q.empty())
    {
        nowA = q.front();
        q.pop();
        nowB = q.front();
        q.pop();
        nowC = q.front();
        q.pop();
        
        for(int i = 1; i <= 6; i++)
        {
            int newA = nowA;
            int newB = nowB;
            int newC = nowC;
            
            // A->B
            if(i == 1)
            {
                if(nowA + nowB > B)
                {
                    newA = nowA + nowB - B;
                    newB = B;
                }
                else
                {
                    newB = nowA + nowB;
                    newA = 0;
                }
            }
            // B->A
            else if(i == 2)
            {
                if(nowB + nowA > A)
                {
                    newB = nowB + nowA - A;
                    newA = A;
                }
                else
                {
                    newA = nowB + nowA;
                    newB = 0;
                }
            }
            // A->C
            else if(i == 3)
            {
                if(nowA + nowC > C)
                {
                    newA = nowA + nowC - C;
                    newC = C;
                }
                else
                {
                    newC = nowA + nowC;
                    newA = 0;
                }
            }
            // C->A
            else if(i == 4)
            {
                if(nowC + nowA > A)
                {
                    newC = nowC + nowA - A;
                    newA = A;
                }
                else
                {
                    newA = nowC + nowA;
                    newC = 0;
                }
            }
            // B->C
            else if(i == 5)
            {
                if(nowB + nowC > C)
                {
                    newB = nowB + nowC - C;
                    newC = C;
                }
                else
                {
                    newC = nowB + nowC;
                    newB = 0;
                }
            }
            // C->B
            else if(i == 6)
            {
                if(nowC + nowB > B)
                {
                    newC = nowC + nowB - B;
                    newB = B;
                }
                else
                {
                    newB = nowC + nowB;
                    newC = 0;
                }
            }
            
            if(visited[newA][newB][newC] == 0)
            {
                visited[newA][newB][newC] = 1;
                q.push(newA);
                q.push(newB);
                q.push(newC);
                
                if(newA == 0 && check[newC] == 0)
                {
                    check[newC] = 1;
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2251_input.txt", "r", stdin);
    
    cin >> A >> B >> C;
    
    BFS(0, 0, C);
    
    for(int i = 0; i <= 200; i++)
    {
        if(check[i] == 1)
        {
            cout << i << " ";
        }
    }
     
    return 0;
}
cs
저작자표시

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

[백준 2468] 안전영역 (BFS) (C/C++)  (0) 2019.12.04
[백준 9177] 단어 섞기 (DFS/BFS) (C/C++) (★★)  (0) 2019.12.04
[백준 7562] 나이트의 이동 (BFS) (C/C++)  (0) 2019.12.03
[백준 5014] 스타트 링크 (BFS) (C/C++)  (0) 2019.12.02
[백준 1697] 숨바꼭질 (BFS) (C/C++)  (0) 2019.12.02
#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int total, start, arrive, up, down;
int visited[1000010];
queue<int> q;
 
void BFS()
{
    visited[start] = 1;
    q.push(start);
    
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        
        for(int i = 1; i <= 2; i++)
        {
            int xpos;
            // up
            if(i == 1)
            {
                xpos = x + up;
            }
            // down
            else if(i == 2)
            {
                xpos = x - down;
            }
            
            if(xpos >= 1 && xpos <= total && visited[xpos] == 0)
            {
                visited[xpos] = visited[x] + 1;
                q.push(xpos);
            }
            
            if(xpos == arrive)
            {
                return;
            }
        }
    }
}
 
int main(void)
{
//    freopen("B5014_input.txt", "r", stdin);
    
    cin >> total >> start >> arrive >> up >> down;
    
    BFS();
    
    if(visited[arrive] == 0)
    {
        cout << "use the stairs";
    }
    else
    {
        cout << visited[arrive]-1;
    }
    
    return 0;
}
cs
저작자표시

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

[백준 2468] 안전영역 (BFS) (C/C++)  (0) 2019.12.04
[백준 9177] 단어 섞기 (DFS/BFS) (C/C++) (★★)  (0) 2019.12.04
[백준 7562] 나이트의 이동 (BFS) (C/C++)  (0) 2019.12.03
[백준 2251] 물통 (BFS) (C/C++)  (0) 2019.12.02
[백준 1697] 숨바꼭질 (BFS) (C/C++)  (0) 2019.12.02

+ Recent posts

티스토리툴바