#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int crash;    
}node;
 
int row, col;
int map[110][110];
int visited[110][110][210];
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 && y >= 0 && x < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS(int x, int y, int crash)
{
    q.push({x, y, crash});
    visited[x][y][crash] = 1;
    
    while(!q.empty())
    {
        x = q.front().x;
        y = q.front().y;
        crash = q.front().crash;
        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 && visited[xpos][ypos][crash] == 0 && crash <= row+col-3)
            {
                q.push({xpos, ypos, crash});
                visited[xpos][ypos][crash] = 1;
            }
            else if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 1 && visited[xpos][ypos][crash+1] == 0 && crash+1 <= row+col-3)
            {
                q.push({xpos, ypos, crash+1});
                visited[xpos][ypos][crash+1] = 1;    
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1261_input.txt", "r", stdin);
 
    cin >> col >> row;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            scanf("%1d", &map[i][j]);
        }
    }
    
    BFS(0, 0, 0);
    
    for(int i = 0; i <= row+col-3; i++)
    {
        if(visited[row-1][col-1][i] == 1)
        {
            cout << i;
            break;
        }
    }
    
    return 0;
}
cs
저작자표시

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

[백준 2589] 보물섬 (BFS) (C/C++)  (0) 2020.04.07
[백준 1938] 통나무 옮기기 (BFS) (C/C++) (★★★)  (0) 2020.02.19
[백준 1167] 트리의 지름 (BFS, Tree) (C/C++) (★)  (0) 2020.02.16
[백준 1967] 트리의 지름 (BFS, Tree) (C/C++)  (0) 2020.02.16
[백준 2146] 다리 만들기 (BFS) (C/C++)  (0) 2020.01.28
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <map> 
#include <math.h>
#include <string>
#include <string.h>
#include <stdlib.h>
using namespace std;
 
int N;
vector<pair<int, int>> graph[100010];
int visited[100010];
int Max;
int MaxNode;
 
void BFS(int start)
{
    queue<int> q;
    q.push(start);
    visited[start] = 0;
    
    while(!q.empty())
    {
        start = q.front();
        q.pop();
        
        for(int i = 0; i < graph[start].size(); i++)
        {
            if(visited[graph[start][i].first] == -1)
            {
                visited[graph[start][i].first] = visited[start] + graph[start][i].second;
                q.push(graph[start][i].first);    
                
                if(Max < visited[graph[start][i].first])
                {
                    Max = visited[graph[start][i].first];
                    MaxNode = graph[start][i].first;
                }
            }
        }    
    }
}
 
int main(void)
{
//    freopen("B1167_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        int from, to, weight;
        cin >> from;
        
        while(1)
        {
            cin >> to;
            
            if(to == -1)
            {
                break;
            } 
            else
            {
                cin >> weight;
            }
            
            graph[from].push_back({to, weight});
        }
    }
    
    // 루트에서 가장 먼 노드를 찾음 
    memset(visited, -1, sizeof(visited));
    BFS(1);
    
    // 위에서 찾은 먼 노드에서 가장 먼 노드를 찾음 
    memset(visited, -1, sizeof(visited));
    BFS(MaxNode);
    
    cout << Max;
    
    return 0;
}
cs
저작자표시

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

[백준 1938] 통나무 옮기기 (BFS) (C/C++) (★★★)  (0) 2020.02.19
[백준 1261] 알고스팟 (BFS) (C/C++) (★★)  (0) 2020.02.16
[백준 1967] 트리의 지름 (BFS, Tree) (C/C++)  (0) 2020.02.16
[백준 2146] 다리 만들기 (BFS) (C/C++)  (0) 2020.01.28
[백준 2178] 미로 탐색 (BFS) (C/C++)  (0) 2020.01.28
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <map> 
#include <math.h>
#include <string>
#include <string.h>
#include <stdlib.h>
using namespace std;
 
int N;
vector<pair<int, int>> graph[10010];
int visited[10010];
int Max;
 
void BFS(int start)
{
    queue<int> q;
    q.push(start);
    visited[start] = 0;
    
    while(!q.empty())
    {
        start = q.front();
        q.pop();
        
        for(int i = 0; i < graph[start].size(); i++)
        {
            if(visited[graph[start][i].first] == -1)
            {
                visited[graph[start][i].first] = visited[start] + graph[start][i].second;
                q.push(graph[start][i].first);    
                
                if(Max < visited[graph[start][i].first])
                {
                    Max = visited[graph[start][i].first];
                }
            }
        }    
    }
}
 
int main(void)
{
//    freopen("B1967_input.txt", "r", stdin);
    
    cin >> N;
    
    int from, to, weight;
    while(cin >> from >> to >> weight)
    {
        graph[from].push_back({to, weight});
        graph[to].push_back({from, weight});
    }
    
    for(int i = 1; i <= N; i++)
    {
        memset(visited, -1, sizeof(visited));
        BFS(i);
    }
    
    cout << Max;
    
    return 0;
}
cs
저작자표시

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

[백준 1261] 알고스팟 (BFS) (C/C++) (★★)  (0) 2020.02.16
[백준 1167] 트리의 지름 (BFS, Tree) (C/C++) (★)  (0) 2020.02.16
[백준 2146] 다리 만들기 (BFS) (C/C++)  (0) 2020.01.28
[백준 2178] 미로 탐색 (BFS) (C/C++)  (0) 2020.01.28
[백준 7576] 토마토 (BFS) (C/C++)  (0) 2020.01.26
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <queue>
#include <vector>
using namespace std;
 
int N;
int islandCnt;
int Min = 9999999;
int map[110][110];
int visited[110][110];
 
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 < N && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
// 섬 색칠
void paint(int x, int y, int color)
{
    q.push({x, y});
    map[x][y] = color;
    
    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] == -1)
            {
                q.push({xpos, ypos});
                map[xpos][ypos] = color;
            }
        }    
    }
}
 
void find()
{
    while(!q.empty())
    {
        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 && map[xpos][ypos] == 0 && visited[xpos][ypos] == 0)
            {
                q.push({xpos, ypos});
                visited[xpos][ypos] = visited[x][y] + 1;
            }
            // 다른섬에 도착하는 경우 = 최소 
            else if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 0 && visited[xpos][ypos] == 0)
            {
                visited[xpos][ypos] = visited[x][y] + 1;
                
                int bridgeLen = visited[xpos][ypos] - 2;
                
                if(bridgeLen < Min)
                {
                    Min = bridgeLen;
                }
                
                return;
            }
        }    
    }
}
 
int main(void)
{
//    freopen("B2146_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin >> map[i][j];
            
            // 섬을 번호순대로 색칠하기위해 -1로 맵 수정 
            if(map[i][j] == 1)
            {
                map[i][j] = -1;
            }
        }
    }
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(map[i][j] == -1)
            {
                paint(i, j, ++islandCnt);
            }
        }
    }
    
    for(int k = 1; k <= islandCnt; k++)
    {
        // 초기화 
        queue<pair<int, int>> temp;
        q = temp;
        memset(visited, 0, sizeof(visited));
        
        // 다리 계산 
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                // k번 섬의 좌표 삽입 
                if(map[i][j] == k)
                {
                    q.push({i, j});
                    visited[i][j] = 1;
                }
            }
        }
        
        find();
    }
    
    cout << Min;
    
    return 0;
}
cs
저작자표시

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

[백준 1167] 트리의 지름 (BFS, Tree) (C/C++) (★)  (0) 2020.02.16
[백준 1967] 트리의 지름 (BFS, Tree) (C/C++)  (0) 2020.02.16
[백준 2178] 미로 탐색 (BFS) (C/C++)  (0) 2020.01.28
[백준 7576] 토마토 (BFS) (C/C++)  (0) 2020.01.26
[백준 1707] 이분 그래프 (BFS) (C/C++) (★)  (0) 2020.01.26
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <queue>
#include <vector>
using namespace std;
 
int row, col;
int map[110][110];
int visited[110][110];
 
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 BFS(int x, int y)
{
    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] == 1 && visited[xpos][ypos] == 0)
            {
                q.push({xpos, ypos});
                visited[xpos][ypos] = visited[x][y] + 1;
            }
        }    
    }
}
 
int main(void)
{
//    freopen("B2178_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            scanf("%1d", &map[i][j]);
        }
    }
    
    BFS(0, 0);
    
    cout << visited[row-1][col-1];
    
    return 0;
}
cs
저작자표시

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

[백준 1967] 트리의 지름 (BFS, Tree) (C/C++)  (0) 2020.02.16
[백준 2146] 다리 만들기 (BFS) (C/C++)  (0) 2020.01.28
[백준 7576] 토마토 (BFS) (C/C++)  (0) 2020.01.26
[백준 1707] 이분 그래프 (BFS) (C/C++) (★)  (0) 2020.01.26
[백준 1525] 퍼즐 (BFS) (C/C++) (★★)  (0) 2019.12.13
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int row, col;
int map[1010][1010];
int visited[1010][1010];
int houseNum;
int Size;
vector<int> complex;
 
queue<pair<int, int>> q;
 
int dx[4] = {-1, 1, 0, 0}; // 상하좌우 
int dy[4] = {0, 0, -1, 1}; // 상하좌우
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0 && visited[i][j] == 0)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS()
{
    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 && map[xpos][ypos] == 0 && visited[xpos][ypos] == 0)
            {
                visited[xpos][ypos] = 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)
            {
                q.push({i, j});
                visited[i][j] = 1;
            }
        }
    }
    
    int time = 0;
    while(1)
    {    
        if(check() == 1)
        {
            cout << time;
            break;
        }
        
        if(q.empty())
        {
            cout << "-1";
            break;
        }
        
        BFS();
        
        time++;    
    }
        
    return 0;
}
cs
저작자표시

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

[백준 2146] 다리 만들기 (BFS) (C/C++)  (0) 2020.01.28
[백준 2178] 미로 탐색 (BFS) (C/C++)  (0) 2020.01.28
[백준 1707] 이분 그래프 (BFS) (C/C++) (★)  (0) 2020.01.26
[백준 1525] 퍼즐 (BFS) (C/C++) (★★)  (0) 2019.12.13
[백준 1963] 소수경로 (BFS) (C/C++)  (0) 2019.12.13
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
 
int T;
int V, E;
vector<int> graph[20010];
int visited[20010];
 
void BFS(int start)
{    
    queue<int> q;
    
    q.push(start);
    visited[start] = 1; // 빨강(1), 파랑(2), 방문X(0) 
    
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        
        for(int i = 0; i < graph[x].size(); i++)
        {
            // 빨강 
            if(visited[x] == 1)
            {
                // 인접한 곳은 파랑으로 색칠
                if(visited[graph[x][i]] == 0)
                {
                    q.push(graph[x][i]);
                    visited[graph[x][i]] = 2;    
                } 
            }
            // 파랑 
            else if(visited[x] == 2)
            {
                // 인접한 곳은 빨강으로 색칠 
                if(visited[graph[x][i]] == 0)
                {
                    q.push(graph[x][i]);
                    visited[graph[x][i]] = 1;    
                } 
            }
        }
    }
}
 
bool isBinary()
{
    for(int i = 1; i <= V; i++)
    {
        for(int j = 0; j < graph[i].size(); j++)
        {
            // 인접한 정점끼리의 색이 같으면 이분그래프X 
            if(visited[i] == visited[graph[i][j]])
            {
                return false;
            }
        }
    }
    
    return true;
}
 
int main(void)
{
//    freopen("B1981_input.txt", "r", stdin);
    
    cin >> T;
    
    while(T--)
    {
        cin >> V >> E;
        
        for(int i = 1; i <= V; i++)
        {
            graph[i].clear();
            visited[i] = 0;
        }
        
        for(int i = 1; i <= E; i++)
        {
            int from, to;
            cin >> from >> to;
            
            graph[from].push_back(to);
            graph[to].push_back(from);
        }
        
        for(int i = 1; i <= V; i++)
        {
            if(visited[i] == 0)
            {
                BFS(i);    
            }
        }
        
        if(isBinary())
        {
            cout << "YES" << endl;    
        } 
        else
        {
            cout << "NO" << endl;
        }
    }
    
    return 0;
}
cs
저작자표시

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

[백준 2178] 미로 탐색 (BFS) (C/C++)  (0) 2020.01.28
[백준 7576] 토마토 (BFS) (C/C++)  (0) 2020.01.26
[백준 1525] 퍼즐 (BFS) (C/C++) (★★)  (0) 2019.12.13
[백준 1963] 소수경로 (BFS) (C/C++)  (0) 2019.12.13
[백준 16236] 아기상어 (BFS) (C/C++) (★★★★)  (0) 2019.12.13
#include <stdio.h>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;
 
string startNum;
string endNum = "123456780";
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 safe(int x, int y)
{
    if(x >= 0 && x < 3 && y >= 0 && y < 3)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS()
{
    visited[startNum] = 1;
    q.push(startNum);
    
    while(!q.empty())
    {
        string num = q.front();
        q.pop();
 
        if(num == endNum)
        {
            flag = true;
            return;
        }
        
        // 빈칸(0)을 찾는 반복문 
        int empty;
        for(int i = 0; i < 9; i++)
        {
            if(num[i] == '0')
            {
                empty = i;
                break;
            }
        }
        
        int x = empty / 3;
        int y = empty % 3;
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1)
            {
                string tempNum = num;
                
                // swap
                char temp = tempNum[3*x+y];
                tempNum[3*x+y] = tempNum[3*xpos+ypos];
                tempNum[3*xpos+ypos] = temp;
                
                if(visited[tempNum] == 0)
                {
                    visited[tempNum] = visited[num]+1;
                    q.push(tempNum);
                }
            }    
        }    
    }
}
 
int main(void)
{
//    freopen("B1525_input.txt", "r", stdin);
    
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            string input;
            cin >> input;
            
            startNum += input;
        }
    }
    
    BFS();
    
    if(flag == true)
    {
        cout << visited[endNum]-1 << endl;
    }
    else
    {
        cout << "-1" << endl;
    }
    
    return 0;
}
cs
저작자표시

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

[백준 7576] 토마토 (BFS) (C/C++)  (0) 2020.01.26
[백준 1707] 이분 그래프 (BFS) (C/C++) (★)  (0) 2020.01.26
[백준 1963] 소수경로 (BFS) (C/C++)  (0) 2019.12.13
[백준 16236] 아기상어 (BFS) (C/C++) (★★★★)  (0) 2019.12.13
[백준 1194] 달이 차오른다, 가자. (BFS, Bitmask) (C/C++) (★★★)  (0) 2019.12.11

+ Recent posts

티스토리툴바